A71358 | 最短路和负环

给出一个有 N 个节点，M 条边的带权有向图。

要求你写一个程序， 判断这个有向图中是否存在负权回路。 如果从一个点沿着某条路径出发， 又回到了自己， 而且所经过的边上的权和小于 0， 就说这条路是一个负权回路。如果存在负权回路， 只输出一行 -1；

如果不存在负权回路， 再求出一个点 S (1≤S≤N)到每个点的最短路的长度。 约定： S 到 S 的距离为 0 , 如果 S 与这个点不连通, 则输出 NoPath。

第一行：点数 N （2≤N≤1000），边数 M （1≤M≤1000），源点 S (1≤S≤N);

以下 M 行，每行三个整数 a, b, c 表示点a, b（1≤a, b≤N）之间连有一条边，权值为 c （-10^6≤c≤10^6）。

请注意：本题两点之间可能存在多条边。

如果存在负权环， 只输出一行-1。

如果不存在负环，请按如下要求输出：

共 N 行，第 i 行描述 S 点到 i 点的最短路: 如果 S 与 i 不连通, 输出 NoPath；如果 i = S，输出 0。

其他情况输出 S 到 i 的最短路的长度。