TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

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$).

Input Format

$N$ $M$ $S$
$a_ 0$ $b_ 0$ $c_ 0$
$a_ 1$ $b_ 1$ $c_ 1$
:
$a_ {M - 1}$ $b_ {M - 1}$ $c_ {M - 1}$

Output Format

$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.

Sample Input 1

4 4 0
0 1 10
0 2 10
0 3 3
3 2 4

Sample Output 1

17
0 0 3 0

Sample Input 2

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

Sample Output 2

24
2 3 1 3 6 4 2

Hints

  • $1 \leq N \leq 2 \times 10^ {5}$
  • $N - 1 \leq M \leq 2 \times 10^ {5}$
  • $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 10^ {9}$
  • All the vertices are reachable from the vertex $S$.

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152