给出一个有N(2≤N≤1,000)个节点，M(M≤100,000)条边的带权有向图。
要求你写一个程序， 判断这个有向图中是否存在负权回路。 如果从一个点沿着某条路径出发， 又回到了自己， 而且所经过的边上的权和小于0， 就说这条路是一个负权回路。如果存在负权回路， 只输出一行-1；
如果不存在负权回路， 再求出一个点S(1≤S≤N)到每个点的最短路的长度。 约定：S到S的距离为0, 如果S与这个点不连通, 则输出NoPath。

第一行：点数N(2≤N≤1,000)，边数M(M≤1,000)，源点S(1≤S≤N);
以下M行, 每行三个整数a, b, c表示点a, b(1≤a, b≤N)之间连有一条边, 权值为c(-1,000,000≤c≤1,000,000)
请注意：本题两点之间可能存在多条边。

如果存在负权环， 只输出一行-1。
如果不存在负环，请按如下要求输出：
共N行， 第i行描述S点到点i的最短路: 如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度。

图论