输入数据给出一个有N（2≤N≤1000）个结点，M（M≤100000）条边的带权有向图。
要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了这个点，而且所经过的边上的权和小于0，就说这条路是一个负权回路。
如果存在负权回路，再求出一个点S（1≤S≤N）到每个点的最短路的长度，约定：S到S的距离为0，如果S与这个点不连通，则输出“No Path”。
第一行：点数N（2≤N≤1000），边数M（M≤100000），源点S（1≤S≤N）。
以下M行，每行三个整数a,b,,c表示点a,b（1≤a,b≤N）之间连有一条边，权值为C（-1000000≤c≤1000000）。
如果存在负权环，只输出一行-1，否则按以下格式输出：
共N行，第i行描述S点到点I的最短路；
如果S与i不连通，输出“No Path”；
如果i=S，输出0；
其他情况输出S到i的最短路的长度。
6 8 7 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
【时限】
Test5 5秒，其余一秒。
一本通