输入数据给出一个有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的最短路的长度。

【时限】

Test5 5秒，其余一秒。

一本通提高