题目描述

原题来自：Vijos P1053

输入数据给出一个有 \(N\) 个节点，\(M\) 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 \(0\)，就说这条路是一个负权回路。

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

输入格式

第一行三个正整数，分别为点数 \(N\)，边数 \(M\)，源点 \(S\)；

以下 \(M\) 行，每行三个整数 \(a, b, c\)，表示点 \(a, b\) 之间连有一条边，权值为 \(c\)。

输出格式

如果存在负权环，只输出一行 \(-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

限制与提示

对于全部数据，\(2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6\)。