Description

Original source: Vijos P1053

The input data provides a weighted directed graph with $N$ nodes and $M$ edges. Your task is to write a program that determines whether this directed graph contains a negative weight cycle. A negative weight cycle is defined as a path that starts and ends at the same node, with the sum of the weights along the edges of the path being less than $0$.

If a negative weight cycle exists, output only one line with $-1$; otherwise, compute the shortest path from a given source node $S$ to every other node. The distance from $S$ to itself is defined as $0$. If $S$ is not connected to a node, output NoPath.

Input Format

The first line contains three positive integers: the number of nodes $N$, the number of edges $M$, and the source node $S$.

The following $M$ lines each contain three integers $a, b, c$, indicating an edge from node $a$ to node $b$ with weight $c$.

Output Format

If a negative weight cycle exists, output only one line with $-1$. Otherwise, output the following:

A total of $N$ lines, where the $i$-th line describes the shortest path from $S$ to node $i$:

• If $S$ is not connected to $i$, output NoPath;
• If $i = S$, output $0$.
• Otherwise, output the length of the shortest path from $S$ to $i$.

Sample 1

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

Data Range and Hints

For all data, $2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6$.