题目背景

这是一道模板题。

题目描述

给定包含$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$​​。