给定一个包含 $N$ 个顶点和 $M$ 条边的简单加权有向图。第 $i$ 条边为 $(a_i, b_i)$，权重为 $c_i$。

求以顶点 $S$ 为根的最小树形图（即从 $S$ 出发可以到达所有顶点）。

数据范围

• $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$
• 顶点 $S$ 可到达所有其他顶点

输入格式

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

输出格式

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

其中 $X$ 是最小树形图中所有边的权重之和，$p_i$ 是顶点 $i$ 的父节点，且令 $p_S = S$。

若存在多个合法的解，输出其中任意一个即可。

样例

输入格式 1

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

输出格式 1

17
0 0 3 0

输入格式 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

输出格式 2

24
2 3 1 3 6 4 2