题目描述

给出一个有 $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$ ($-1,000,000≤c≤1,000,000$)
请注意：本题两点之间可能存在多条边。

输出

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