Given a simple weighted directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_ i, b_ i)$ and has a weight of $c_ i$.
Find the directed minimum spanning tree whose root is the vertex $S$ (it means that all the vertices have to be reachable from $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$ is the sum of the weights of the edges in the directed MST. $p_ i$ is the parent of the vertex $i$ or $p_ S = S$.
If there are multiple correct output, print any of them.
4 4 0 0 1 10 0 2 10 0 3 3 3 2 4
17 0 0 3 0
7 8 3 3 1 10 1 2 1 2 0 1 0 1 1 2 6 10 6 4 1 4 5 1 5 6 1
24 2 3 1 3 6 4 2
| No. | Testdata Range | Score |
|---|