该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给出 $N$ 个节点、$M$ 条边的带权有向图。判断图中是否存在负权回路。

若存在负权回路，只输出 $-1$；

若不存在负权回路，求出点 $st$ 到 每个点的最短路的长度。

【输入格式】

第一行三个正整数 $N,M,st$（$2 \le N \le 1000,1 \le M \le 10^5$） 。

下来 $M$ 行，每行三个整数 $x,y,w$，表示点 $x$ 到 点 $y$ 权值为 w 的有向边（$|w| \le 10^6$）。

【输出格式】

如果存在负权环，只输出一行 $-1$，否则按以下格式输出： 共 $N$ 行，第 $i$ 行描述 $st$ 点到点 $i$ 的最短路。

约定：

$st$ 到 $st$ 的距离为 $0$。

如果 $st$ 与点 $i$ 不连通，则输出 $NoPath$ 。

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