【模板】最小树形图

题目背景

这是一道模板题。

题目描述

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

输入输出格式

输入格式


第一行包含三个整数 $n,m,r$,意义同题目所述。 接下来 $m$ 行,每行包含三个整数 $u,v,w$,表示图中存在一条从 $u$ 指向 $v$ 的权值为 $w$ 的有向边。

输出格式


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

输入输出样例

输入样例 #1

4 6 1
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

输出样例 #1

3

输入样例 #2

4 6 3
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

输出样例 #2

4

输入样例 #3

4 6 2
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

输出样例 #3

-1

说明

**样例 $1$ 解释** 最小树形图中包含第 $2$, $5$, $6$ 三条边,总权值为 $1 + 1 + 1 = 3$ **样例 $2$ 解释** 最小树形图中包含第 $3$, $5$, $6$ 三条边,总权值为 $2 + 1 + 1 = 4$ **样例 $3$ 解释** 无法构成最小树形图,故输出 $-1$ 。 **数据范围** 对于所有数据,$1 \leq u, v \leq n \leq 100$, $1 \leq m \leq 10^4$​​, $1 \leq w \leq 10^6$​​。