测试数据来自 system/1696

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出包含 \(n\) 个点的混合图（编号为 \(1..n\)），该图含 \(m\) 条正权无向边，\(p\) 条负权有向边。请你计算从 \(1\) 到各点最短路径长度，如果不存在最短路径（可以无穷短），输出‘NONE’。

【输入格式】

　　第 1 行包含 3 个正整数：\(n,m,p\)。
　　接下来 \(m\) 行每行输入三个整数 \(a,b,c\)，表示点 \(a\) 到点 \(b\) 的边的长度为 \(c\)。
　　再接下来 \(p\) 行，每行输入三个整数 \(a,b,c\)，表示一条起点为 \(a\)，终点为 \(b\) 的有向边，边的长度为 \(c(<0)\)。

【输出格式】

　　如果不存在最短路径（负权回路），则输出'NONE'，否则输出 \(n\) 行，其中第 \(i\) 行表示 \(1\) 到点 \(i\) 的最短路径长度（如果 \(1\) 不能走到 \(i\)，则输出 \(inf\)）。

【输入输出样例1】

　Input

5 5 1
1 2 1
1 3 3
2 4 2
4 5 2
1 5 8
3 2 -3

　Output

0
0
3
2
4

【输入输出样例2】

　Input

5 5 2
1 2 1
1 3 3
2 4 2
4 5 2
1 5 8
3 2 -3
5 3 -2

　Output

NONE

【数据限制】

　　\(100\%\) 的数据满足，\(1≤n≤500\) ， \(1≤m≤2500\) ， \(1≤p≤200\)， \(1≤|c|≤10000\)。

【来源】

　　Mr.he