P4716 [Template] Minimum Arborescence

This is a template problem.

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$.

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$.

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$.

**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