#ASAPORO2E. Black Cats Deployment

Black Cats Deployment

配点 : 800800

問題文

すぬけフェスティバル2017が 1,2,...,N1,2, ...,N の番号がついた NN 頂点の木で開催されます。 この木の ii 番目の辺は頂点 aia_ibib_i をつなぐ楽しさ cic_i の辺です。

すぬけくんと N1N-1 匹の黒猫がスタッフです。 すぬけくんはある頂点に本部を設置し、それ以外の N1N-1 個の頂点にそれぞれ黒猫を 11 匹派遣しようと考えています。

全ての頂点について、その頂点に本部を設置したときの 良さ を計算してください。 頂点 ii に本部を置いたときの良さは以下のようにして計算されます。

  • X=0X=0 とする
  • 11 以上 NN 以下の整数 jj (ただし ii を除く)について、以下の処理を行う- 頂点 ii から頂点 jj への経路の途中にある辺のうち、最も楽しさが小さいような辺の楽しさ ccXX に加算する
  • 頂点 ii から頂点 jj への経路の途中にある辺のうち、最も楽しさが小さいような辺の楽しさ ccXX に加算する
  • 最終的な XX の値が良さである

制約

  • 1N1051 \leq N \leq 10^{5}
  • 1ai,biN1 \leq a_i,b_i \leq N
  • 1ci1091 \leq c_i \leq 10^{9}
  • 与えられるグラフは木
  • 与えられる入力は全て整数

部分点

  • 200200 点分のデータセットでは N1000N \leq 1000 が成立する
  • 200200 点分のデータセットでは ci2c_i \leq 2 が成立する

入力

入力は以下の形式で標準入力から与えられる。

NN

a1a_1 b1b_1 c1c_1

::

aN1a_{N-1} bN1b_{N-1} cN1c_{N-1}

出力

NN 行に答えを出力せよ。 ii 行目には頂点 ii に本部を設置したときの良さを出力せよ。

3
1 2 10
2 3 20
20
30
30
  • 以下の図に頂点 1,2,31,2,3 に本部を設置した場合をそれぞれ示します
  • 辺の上に書かれた数はその辺の楽しさを、頂点の下に書かれた数は本部からその頂点への経路の途中にある辺のうち、最も楽しさが小さいような辺の楽しさを示します

1ee10aa2a1bf5e43e05161f37d88bdc1.png

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2
16
20
15
14
20
15
16
20
15
20
20
20
16
15
20
19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14
103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370