Minimum Spanning Arborescence

Given a directed graph with \(n\) nodes and \(m\) edges, determine the minimum spanning arborescence rooted at node \(r\). An arborescence is a spanning tree where every node (except the root) has exactly one incoming edge. The cost of an arborescence is the sum of the weights of its edges. In case a spanning arborescence rooted at \(r\) does not exist, output \(-1\).

You are given an integer \(n\), the number of nodes, an integer \(m\), the number of directed edges, and an integer \(r\) (the root). Following that are \(m\) lines each containing three integers \(u, v, w\) representing a directed edge from node \(u\) to node \(v\) with weight \(w\).

Note: All formulas are written in \(\LaTeX\) format. You may assume that the nodes are numbered from 1 to \(n\).

inputFormat

The first line contains three space-separated integers: \(n\), \(m\), and \(r\), where \(n\) is the number of nodes, \(m\) is the number of directed edges, and \(r\) is the root node.

The following \(m\) lines each contain three space-separated integers \(u\), \(v\), and \(w\), denoting a directed edge from node \(u\) to node \(v\) with weight \(w\).

outputFormat

Output a single integer: the sum of the weights of the edges in the minimum spanning arborescence rooted at \(r\). If such an arborescence does not exist (i.e. not all nodes are reachable), output \(-1\).

sample

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

3