유향 MST

$N$개의 정점과 $M$개의 간선을 갖는 단순 가중 유향 그래프가 주어진다. $i$번째 간선은 $(a_i, b_i)$이고 가중치는 $c_i$이다.

정점 $S$을 루트로 하는 유향 최소 스패닝 트리를 구한다(이는 모든 정점이 $S$에서 도달 가능해야 한다는 뜻이다).

제한 조건

• $1 \leq N \leq 200000$
• $N - 1 \leq M \leq 200000$
• $0 \leq S < N$
• $0 \leq a_i, b_i < N$
• $a_i \neq b_i$
• $(a_i, b_i) \neq (a_j, b_j) (i \neq j)$
• $0 \leq c_i \leq 1000000000$
• 모든 정점은 정점 $S$에서 도달 가능하다.

$N$ $M$ $S$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
:
$a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$

$X$
$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$

$X$은 유향 MST에 포함된 간선들의 가중치 합이다. $p_i$은 정점 $i$의 부모이거나 $p_S = S$이다.

올바른 출력이 여러 개라면 그중 아무거나 출력한다.