原題來自：Vijos P1053
輸入數(shù)據(jù)給出一個有 N 個節(jié)點，M 條邊的帶權(quán)有向圖。要求你寫一個程序，判斷這個有向圖中是否存在負權(quán)回路。如果從一個點沿著某條路徑出發(fā)，又回到了自己，而且所經(jīng)過的邊上的權(quán)和小于 0，就說這條路是一個負權(quán)回路。
如果存在負權(quán)回路，只輸出一行 ?1；如果不存在負權(quán)回路，再求出一個點S到每個點的最短路的長度。約定：S 到 S 的距離為 0，如果 S 與這個點不連通，則輸出 NoPath。

第一行三個正整數(shù)，分別為點數(shù) N，邊數(shù) M，源點 S；
以下 M 行，每行三個整數(shù) a,b,c，表示點 a,b 之間連有一條邊，權(quán)值為 c。

如果存在負權(quán)環(huán)，只輸出一行 ?1，否則按以下格式輸出：
共 N 行，第 i 行描述 S 點到點 i 的最短路：
如果 S 與 i 不連通，輸出 NoPath；
如果 i=S，輸出 0。
其他情況輸出 S 到 i 的最短路的長度。

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

0
6
4
-3
-2
7

數(shù)據(jù)范圍：
對于全部數(shù)據(jù)，2≤N≤1000,1≤M≤10⁵,1≤a,b,S≤N,∣c∣≤10⁶。