有向最小生成树（Directed MST）

问题描述

给定一个含 $N$ 个顶点、$M$ 条边的简单有向加权图，以及一个指定根节点 $S$（$0 \le S < N$）。
要求构造一棵以 $S$ 为根的有向最小生成树（Directed Minimum Spanning Tree, DMST），即：

• 包含所有 $N$ 个顶点；
• 恰好 $N-1$ 条边；
• 从根 $S$ 到任意其他顶点有且仅有一条有向路径（即形成一棵以 $S$ 为根的外向树）；
• 总边权最小。

输出该树的总权重 $X$，以及每个非根顶点 $i$ 的父节点 $p_i$（即边 $p_i \to i$ 属于树），其中规定 $p_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 \ne b_i$
• $0 \leq c_i \leq 10^9$
• 所有顶点均可从 $S$ 到达

输入

$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\ \cdots\ p_{N-1}$

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

17
0 0 3 0

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

24
2 3 1 3 6 4 2