题目描述

原题来自：[Vijos P1053]

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

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

输入格式

第一行三个正整数，分别为点数$\red{ N}$，边数 $\red{M}$，源点 $\red{S}$；

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

输出格式

如果存在负权环，只输出一行 $\red{-1}$，否则按以下格式输出：

共 $\red{N }$行，第 $\red{i}$ 行描述$\red{ S }$点到点$\red{ i}$ 的最短路：

如果 $\red{S }$与$\red{ i }$不连通，输出 NoPath； 如果 $\red{i=S}$，输出 $\red{0}$。 其他情况输出$\red{ S }$到 $\red{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

提示

对于全部数据，$\red{2\le N\le 100,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6}$。