Given a weighted directed graph with $n$ vertices and $m$ edges, where weights may be negative, find the shortest path from the starting vertex $s$ to all other vertices.

Input

The first line contains three space-separated integers $n$, $m$, and $s$.

The following $m$ lines each contain three integers $s_i$, $t_i$, and $w_i$ ($1 \le s_i, t_i \le n$, $-10^9 \leq w_i \leq 10^9$), representing a directed edge from $s_i$ to $t_i$ with weight $w_i$. The graph may contain multiple edges or self-loops.

Output

Output a single line containing $n$ integers $d_1, d_2, \ldots, d_n$, where $d_i$ is the shortest path distance from $s$ to $i$. If no such path exists, output N/A. If the shortest path is negative infinity, output -inf.

Examples

Input 1

4 5 1
1 2 1000
2 3 10000
3 1 1
3 4 100000
3 4 1000000

Output 1

0 1000 11000 111000

Input 2

4 4 2
1 2 1
2 3 1000000000
3 4 -1
4 3 -1

Output 2

N/A 0 -inf -inf

Subtasks

For all data, $1 \le n \le 5\,000$ and $0 \le m \le 3 \cdot 10^5$.