U277830 【MOVE0015】送分题

此题为本人搜集，有版权问题，请联系。

给出一个n 个顶点m 条边的有向图，顶点编号为1~n。判断这个有向图中是否存在 负权回路，如果不存在，则输出一个源点s 到其他点的最短距离。

第一行两个整数n，m，s,表示有n 个点，m 条边，源点编号为s；\ 下面的m 行每行3 个正整数u, v, w, 表示顶点u, v 之间有一条长度为w 的有向边。

如果存在负权环，只输出一行-1，否则按以下格式输出：\ 共N 行，第i 行描述S 点到点i 的最短路：如果S 与i 不连通，输出NoPath； 如果i = S，输出0。其他情况输出S 到i 的最短路的长度。

$$1