有向图最小树形图

【题目描述】

给定一个有 $N$ 个顶点、$M$ 条边的简单带权有向图。第 $i$ 条边为 $(a_i, b_i)$，权值为 $c_i$。

请找出根为顶点 $S$ 的有向最小生成树（这意味着所有顶点都必须从 $S$ 可达）。

【输入】

第一行包含三个整数 $N$、$M$、$S$。

接下来 $M$ 行，第 $i$ 行包含三个整数 $a_i$、$b_i$、$c_i$，表示一条从 $a_i$ 到 $b_i$、权值为 $c_i$ 的边。

$N$ $M$ $S$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
:
$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$。

如果有多个正确输出，输出其中任意一个。

【输入样例】

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

【输出样例】

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

【数据范围】

• $1 \leq N \leq 200000$
• $N - 1 \leq M \leq 200000$
• $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 1000000000$
• 所有顶点都可以从顶点 $S$ 到达。

【来源】

Library Checker（yosupo06） directedmst

本题为 special judge（输出任意合法解），暂不可本地评测。