Migrated from Lutece 2733 建设道路2

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

图图国又新建了 $n$ 座城市，图图国王准备将第 $r$ 座城市定为首都。图图国中的工程师经过勘测后，向国王汇报了在这 $n$ 座城市之间有 $m$ 条单向道路可以建成，其中第 $i$ 条道路从第 $u_i$ 座城市通往第 $v_i$ 座城市，建成这条道路的代价为 $w_i$ 。图图国王将勘测报告给你，并向你询问在这 $m$ 条道路中选取 $n-1$ 条道路，使得从第 $r$ 座城可以通过这些单向道路通往每一座城市的最小代价为多少，如果不能达成目标，输出 $-1$。

Input

第一行为是三个整数 $n$ , $m$ , $r$ ，分别代表有 $n$ 个国家，$m$ 条道路，首都位于第 $r$ 座城市 第二行起 $m$ 行，每行三个非负整数 $u_i$，$v_i$，$w_i$，表示从第 $u_i$ 座城到第 $v_i$ 座城有一条权值为 $w_i$ 的有向道路。

Output

如果能达成目标，输出一个整数表示最小代价，否则输出 $-1$ 。

Samples

5 10 1
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1
1 5 3
2 5 4
5 3 2
5 4 1

6

Constraints

$1 \leq n \leq 100$ $1 \leq m \leq 10000$ $1 \leq u_i,v_i \leq n$ $1 \leq w_i \leq 10^6$

Note

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

Resources

2022 UESTC ICPC Training for Graph