原题来自：Vijos P1053
Vijos P1053
输入数据给出一个有 N 个节点，M 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。
N
M
0
如果存在负权回路，只输出一行 −1；如果不存在负权回路，再求出一个点S到每个点的最短路的长度。约定：S 到 S 的距离为 0，如果 S 与这个点不连通，则输出 NoPath。
−1
S
NoPath
第一行三个正整数，分别为点数 N，边数 M，源点S；
以下 M 行，每行三个整数a,b,c，表示点 a,b 之间连有一条边，权值为c。
a,b,c
a,b
c
如果存在负权环，只输出一行−1，否则按以下格式输出：
共 N行，第 i 行描述 S 点到点 i 的最短路：
i
如果 S 与i 不连通，输出 NoPath；
如果 i=S，输出 0。
i=S
其他情况输出 S 到 i 的最短路的长度。
样例输入
6 8 11 3 41 2 63 4 -76 4 22 4 53 6 34 5 13 5 4
样例输出
064-3-27
对于全部数据， 2≤N≤1000,1≤M≤10^5,1≤a,b,S≤N,∣c∣≤10^6 。
做这道题时，你不必为超时担心，不必为不会算法担心，但是如此「简单」的题目，你究竟能 AC 么？
