#3149. 最小树形图 暂未评定

这是一道模板题。

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

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

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

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

样例输入1

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

样例输出 1

3

样例解释 1

最小树形图中包含第 ， ， 三条边，总权值为

样例输入 2

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

样例输出 2

4

样例输出 2

最小树形图中包含第 ， ， 三条边，总权值为

样例输入 3

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

样例输出 3

-1

样例解释 3

无法构成最小树形图，故输出 。

对于所有数据， 。