Problem Background

This is a template problem.

Problem Description

Given a graph with $n$ nodes and $m$ directed edges, find a Minimum Spanning Tree (MST) rooted at node $r$ and output the sum of the weights of the edges in the MST. If there is no MST rooted at $r$, output $-1$.

Input Format

The first line contains three integers $n$, $m$, and $r$, which represent the number of nodes, the number of edges, and the root node, respectively.

The following $m$ lines each contain three integers $u$, $v$, and $w$, indicating that there is a directed edge from node $u$ to node $v$ with weight $w$.

Output Format

If there exists an MST rooted at $r$, output the sum of the weights of the edges in the MST. Otherwise, output $-1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

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

Sample Output #2

4

Sample Input #3

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

Sample Output #3

-1

Notes

Sample 1 Explanation

The MST includes the 2nd, 5th, and 6th edges, with a total weight of $1 + 1 + 1 = 3$.

Sample 2 Explanation

The MST includes the 3rd, 5th, and 6th edges, with a total weight of $2 + 1 + 1 = 4$.

Sample 3 Explanation

No MST can be formed, so the output is $-1$.

Data Range

For all data, $1 \leq u, v \leq n \leq 100$, $1 \leq m \leq 10^4$, $1 \leq w \leq 10^6$.

见题面 Input 部分

见题面 Output 部分