QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
[+1]

# 904. 最小树形图

Statistics

Source: Library Checker

Statement

Given a simple weighted directed graph with N vertices and M edges. i-th edge is (ai,bi) and has a weight of ci.

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 辺の単純な重み付き有向グラフが与えられる。i 番目の辺は頂点 ai から bi に貼られており、重さ ci である。

頂点 S を根とする(根から全ての頂点に到達できる)有向最小全域木を求めよ。

Constraint

  • 1N2×105
  • N1M2×105
  • 0S<N
  • 0ai,bi<N
  • aibi
  • (ai,bi)(aj,bj)(ij)
  • 0ci109
  • All the vertices are reachable from the vertex S (頂点 S から全ての頂点へ到達可能)

Input

  • N M S
  • a0 b0 c0
  • a1 b1 c1
  • :
  • aM1 bM1 cM1

Output

  • X
  • p0 p1 p2 ... pN1

X is the sum of the weights of the edges in the directed MST. pi is the parent of the vertex i or pS=S.

If there are multiple correct output, print any of them.

ただし、X は木の重みの総和であり、pi は頂点 i の親である。pS=S とすること。

解が複数存在する場合、どれを返しても構わない。

Example

Input 1

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

Output 1

17
0 0 3 0

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

Output 2

24
2 3 1 3 6 4 2