E - 不可視境界線 (The Invisible Borderline) Editorial /

Time Limit: 2 sec / Memory Limit: 128 MB

この問題の入力例1の図が間違っていましたが、修正しました。
また、入力例2のほうはジャッジシステムで使っているものと異なっていたので、変更しました。ただ、今までのテストケースも問題の条件は満たしていました。
リジャッジも終わりました。

問題文

ダンジョンを抜けるとそこは学校だった。
その学校は部活動が盛んなようだったので、joisinoお姉ちゃんは部活見学をしてみることにした。

はじめに入った部活では床に魔方陣が描かれていた。
何をしているのかたずねてみると、異世界についての研究をしているという。
彼女たちの話によると、この世界を含めたN個の世界が存在していて、それらはN-1個の不可視境界線と呼ばれるゲートのようなものでつながっているということである。
また、世界同士はいくつかの不可視境界線を通ることによって互いに行き来できるようになっているらしい。
そして、不可視境界線i(1 ≦ i ≦ N-1)は世界A_i(1 ≦ A_i ≦ N)とB_i(1 ≦ B_i ≦ N)を結んでいるが、通るときにC_i(1 ≦ C_i ≦ 10^9)のダメージを受けるという。

そこで彼女たちはそれぞれの世界について、合計で最も多くのダメージを受けないとたどり着くことのできない世界を探しているらしい。

しかし、世界はたくさんあるので、彼女たちは調べるのがとても大変そうである。
そこでjoisinoお姉ちゃんはこの問題を解くプログラムを書いてあげることにした。

入力

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

N
A_1 B_1 C_1
A_2 B_2 C_2
：
A_{N-1} B_{N-1} C_{N-1}
  • 1行目には、世界の数N(1 ≦ N ≦ 10^5)が与えられる。
  • 2行目からのN-1行のうちi行目にはi番目の道の情報が書かれており、A_iとB_iとC_iが空白区切りで与えられる。

配点

この問題に部分点はない。 正解すると80点を得られる。

出力

出力はN行からなる。
i行目にはi番目の世界から最も多くのダメージを受けないとたどり着くことのできない世界の番号を出力せよ。
また、そのような世界が複数あるときはそれらの番号の中で最も小さいものを出力せよ。
出力の末尾にも改行を入れること。

入力例1

3
1 2 10
2 3 15

出力例1

3
3
1

この場合、下の図のように世界はつながっていて、世界1からは世界3へ行く時が25とダメージの合計が最も多く、世界2からは世界3へ行くとき15とダメージの合計が最も多く、世界3からは世界1に行くときが25とダメージの合計が最も多い。

入力例2

5
1 2 15
1 3 15
1 4 5
4 5 10

出力例2

2
3
2
2
2

この場合、下の図のように世界はつながっていて、世界1からは世界2へ、世界2からは世界3へ、世界3からは世界2へ、世界4からは世界2へ、世界5からは世界2へ行くのがもっとも多くダメージを受ける。

入力例3

10
8 3 55
9 1 160
1 4 265
9 5 571
2 9 771
4 7 818
9 10 11
2 8 569
4 6 340

出力例3

3
7
7
3
3
3
3
7
3
3