1608_最小树形图

这是一道模板题。

给定包含 n 个节点，m 条有向边的一个图。试求一棵以节点 r 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 r 为根的最小树形图，输出 −1。

第一行包含三个整数 n, m, r，意义同题目所述。

接下来 m 行，每行包含三个整数 u, v, w，表示图中存在一条从 u 指向 v 的权值为 w 的有向边。

对于所有数据，1 ≤ u , v ≤ n ≤ 100  ,   1 ≤ m ≤ 10⁴  ,    1 ≤ w ≤ 10⁶ 。

如果原图中存在以 r 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 −1。

Sample #1
4 6 1
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

Sample #2
4 6 3
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

Sample #3
4 6 2
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

Sample #1
3

Sample #2
4

Sample #3
-1

Sample #1
最小树形图中包含第 2， 5， 6 三条边，总权值为 1+1+1=3

Sample #2
最小树形图中包含第 3， 5， 6 三条边，总权值为 2+1+1=3

Sample #3
无法构成最小树形图，故输出 −1 。