Given a simple weighted directed graph with $N$ vertices and $M$ edges. The $i$-th edge is $(a_i, b_i)$ and has a weight of $c_i$.

Find the directed minimum spanning tree rooted at vertex $S$ (this means all vertices must be reachable from $S$).

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $N - 1 \leq M \leq 2 \times 10^5$
• $0 \leq S < N$
• $0 \leq a_i, b_i < N$
• $a_i \neq b_i$
• $(a_i, b_i) \neq (a_j, b_j) (i \neq j)$
• $0 \leq c_i \leq 10^9$
• All vertices are reachable from vertex $S$

Input

$N$ $M$ $S$ $a_0$ $b_0$ $c_0$ $a_1$ $b_1$ $c_1$ : $a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$

Output

$X$ $p_0$ $p_1$ $p_2$ ... $p_{N - 1}$

$X$ is the sum of the weights of the edges in the directed MST. $p_i$ is the parent of vertex $i$, with $p_S = S$.

If there are multiple correct outputs, print any of them.

Examples

Input 1

4 4 0
0 1 10
0 2 10
0 3 3
3 2 4

Output 1

17
0 0 3 0

Input 2

7 8 3
3 1 10
1 2 1
2 0 1
0 1 1
2 6 10
6 4 1
4 5 1
5 6 1

Output 2

24
2 3 1 3 6 4 2