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

---

【题目描述】

　　输入数据给出一个有 \(N\) 个节点，\(M\) 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。

　　如果存在负权回路，只输出一行 −1；如果不存在负权回路，再求出一个点 \(S\) 到每个点的最短路的长度。约定：\(S\) 到 \(S\) 的距离为 0，如果 \(S\) 与这个点不连通，则输出 NoPath。

【输入格式】

　　第一行三个正整数，分别为点数 \(N\)，边数 \(M\)，源点 \(S\)；
　　以下 \(M\) 行，每行三个整数 \(a,b,c\)，表示点 \(a,b\) 之间连有一条边，权值为 \(c\)。

【输出格式】

　　如果存在负权环，只输出一行 −1，否则按以下格式输出：共 \(N\) 行，第 \(i\) 行描述 \(S\) 点到点 \(i\) 的最短路：
　　如果 \(S\) 与 \(i\) 不连通，输出 NoPath；
　　如果 \(i=S\)，输出 0。
　　其他情况输出 \(S\) 到 \(i\) 的最短路的长度。

【输入输出样例】

　Input

6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

　Output

0
6
4
-3
-2

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤N≤1000\)，\(1≤M≤10^5\)，\(1≤a,b,S≤N\)，\(|c|≤10^6\)

【来源】

　　Mr.he