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

---

【问题描述】

　　 负权回路： 如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。

　　现在给出一个有 \(n\) 个顶点、 \(m\) 条边的带权有向图。请写一个程序，判断这个有向图中是否存在负权回路。

【输入格式】

　　第一行三个正整数，分别为点数 \(n\)，边数 \(m\)，源点 \(s\)；
　　以下 \(m\) 行，每行三个整数 \(u, v, w\)，表示从点 \(u\) 到 \(v\) 有一条权值为 \(w\) 的有向边。

【输出格式】

　　如果存在负权环，只输出一行 -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
7

【数据限制】

　　对于全部数据，\(2\le n\le 1000，1\le m\le 10^5,1\le u,v,w\le n,|w|\le 10^6\)。

【来源】

　Mr.he