Background

This is a template problem.

Problem Description

Given a directed graph with $n$ nodes and $m$ directed edges. Find a minimum arborescence rooted at node $r$, and output the sum of the weights of all edges in the minimum arborescence. If there is no minimum arborescence rooted at $r$, output $-1$.

Input Format

The first line contains three integers $n, m, r$, with the same meanings as described in the statement.

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

Output Format

If the original graph has a minimum arborescence rooted at $r$, output the sum of the weights of all edges in the minimum arborescence; otherwise output $-1$.

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

3

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

4

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

-1

Hint

Sample $1$ Explanation

The minimum arborescence contains edges $2$, $5$, and $6$, with total weight $1 + 1 + 1 = 3$.

Sample $2$ Explanation

The minimum arborescence contains edges $3$, $5$, and $6$, with total weight $2 + 1 + 1 = 4$.

Sample $3$ Explanation

A minimum arborescence cannot be formed, so output $-1$.

Constraints

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

Translated by ChatGPT 5