Given a weighted directed graph with $n$ vertices and $m$ edges, 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 positive integers $s_i$, $t_i$, and $w_i$ ($1 \le s_i, t_i \le n$, $0 \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 between the same pair of vertices or self-loops.

Output

Output a single line containing $n$ integers $d_1, d_2, \ldots, d_n$, where $d_i$ is the length of the shortest path from $s$ to $i$. If no such path exists, output $-1$.

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

2 1 2
1 2 1

Output 2

-1 0

Subtasks

For all test cases, $1 \le n \le 3 \cdot 10^5$ and $0 \le m \le 10^6$.