최소 스패닝 아보레선스

Arborescence $G=(V,A)$는 다음 조건을 만족하는 방향 그래프이다.

• 모든 정점 $v \in V$에 대해 정점 $r$에서 정점 $v$로 가는 경로가 존재하는 정점 $r \in V$가 있다. 이 정점 $r$을 루트 노드(root node)라고 한다.
• $A$의 방향을 없앤 간선 집합을 $E$라 할 때, 무방향 그래프 $G'=(V,E)$는 트리이다.

간선에 가중치가 있고 사이클이 없는 방향 그래프 $G=(V,A)$와 정점 $r$이 주어진다. 각 정점에는 1부터 $N$까지 번호가 붙어 있다. 이때 정점 $r$을 루트로 하는 Spanning Arborescence 중 간선 가중치의 합이 최소인 것을 구한다.

이와 관련된 알고리즘으로, $O(|V||A|)$에 동작하는 Chu-Liu-Edmonds' 알고리즘이 있고, Tarjan이 이를 개선해 시간 복잡도를 $O(|A| \log |V|)$로 줄인 알고리즘이 있다. 다만 이 문제가 그 알고리즘을 쓰라고 낸 것은 아니다.

주어진 그래프에서 루트를 $r$로 하는 Spanning Arborescence의 간선 가중치 합의 최솟값을 구한다.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 루트로 삼을 정점 번호 $r$이 공백으로 구분되어 주어진다. ($1 \le N \le 500\,000$; $0 \le M \le 1\,000\,000$; $1 \le r \le N$)

두 번째 줄부터 $M$개의 줄에 걸쳐 간선 정보가 주어진다. 각 줄에는 세 정수 $u$, $v$, $c$가 공백으로 구분되어 있으며, 가중치가 $c$인 정점 $u$에서 정점 $v$로 가는 간선이 있다는 뜻이다. ($1 \le u, v \le N$; $u \ne v$; $1 \le c \le 1\,000\,000\,000$)

주어진 그래프에서 임의의 두 정점을 잇는 간선은 최대 한 개이며, 사이클은 존재하지 않는다.

정점 $r$을 루트로 하는 Spanning Arborescence의 간선 가중치 합의 최솟값을 출력한다. 정점 $r$을 루트로 하는 Spanning Arborescence가 없으면 -1을 출력한다.