AT_tkppc2015_e 不可視境界線 (The Invisible Borderline)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_e この問題の入力例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 $が空白区切りで与えられる。

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

### 配点 この問題に部分点はない。 正解すると80点を得られる。 ### Sample Explanation 1 この場合、下の図のように世界はつながっていて、世界$ 1 $からは世界$ 3 $へ行く時が$ 25 $とダメージの合計が最も多く、世界$ 2 $からは世界$ 3 $へ行くとき$ 15 $とダメージの合計が最も多く、世界$ 3 $からは世界$ 1 $に行くときが$ 25 $とダメージの合計が最も多い。 !\[\](/img/other/tsukukoma2015/asasffewe/g12.jpg) ### Sample Explanation 2 \### 出力例2 ``` 2 3 2 2 2 ``` この場合、下の図のように世界はつながっていて、世界$ 1 $からは世界$ 2 $へ、世界$ 2 $からは世界$ 3 $へ、世界$ 3 $からは世界$ 2 $へ、世界$ 4 $からは世界$ 2 $へ、世界$ 5 $からは世界$ 2 $へ行くのがもっとも多くダメージを受ける。 !\[\](/img/other/tsukukoma2015/asasffewe/g2.jpg)