负权回路
测试数据来自 system/3096
作业已超过截止时间，您无法递交本题目。
时间限制：1秒 内存限制：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\)。