Minimum Spanning Arborescence

An arborescence $G=(V,A)$ is a directed graph that satisfies the following conditions.

• There is a vertex $r \in V$ such that for every vertex $v \in V$, there is a path from $r$ to $v$. This vertex $r$ is called the root node.
• Let $E$ be the set of edges of $A$ with their directions removed. The undirected graph $G'=(V,E)$ is a tree.

You are given a directed graph $G=(V,A)$ with weighted edges and no cycles, along with a vertex $r$. Each vertex is numbered from $1$ to $N$. You need to find the minimum total edge weight among all spanning arborescences whose root node is $r$.

The Chu-Liu-Edmonds' algorithm runs in $O(|V||A|)$, and Tarjan's improvement of it runs in $O(|A| \log |V|)$. However, this problem does not ask you to use that algorithm.

Find the minimum total weight of a spanning arborescence rooted at $r$ in the given graph.

The first line contains the number of vertices $N$, the number of edges $M$, and the root vertex $r$, separated by spaces. ($1 \le N \le 500\,000$; $0 \le M \le 1\,000\,000$; $1 \le r \le N$)

From the second line through the $(M+1)$-th line, each line contains three integers $u$, $v$, and $c$, separated by spaces. This means there is an edge from vertex $u$ to vertex $v$ with weight $c$. ($1 \le u, v \le N$; $u \ne v$; $1 \le c \le 1\,000\,000\,000$)

Any two vertices are connected by at most one edge in the given graph, and the graph has no cycles.

Print the minimum total edge weight of a spanning arborescence rooted at $r$. If no spanning arborescence rooted at $r$ exists, print -1.