9583 - 最小树形图

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

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

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

如果原图中存在以 r 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 -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​​。