No.807 umg tours

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 140
作問者 : sinsincoscossinsincoscos / テスター : tempura_pptempura_pp
23 ProblemId : 2822 / 出題時の順位表

問題文

 umg toursでは,$N$個のスポットでのツアーを企画しています。道が$M$個あり,道$i$は,異なる2つのスポット$a_i$と$b_i$の間を距離$c_i$で双方向に結んでいます。 どの2つのスポット間も道を経由することで行き来できることが保証されます。また,同じスポットを結ぶ道が2本以上存在することもありません。
 umgくんは$N$個のツアーを企画しました。ツアー$i$では,スポット$1$から始め,道を移動しながらスポット$i$を訪問した後,再びスポット$1$に戻ってきます。 行きと帰りとで経路が異なっていてもよいです。
 ある日,$N$人のツーリストがumg toursを利用しに来ました。ツーリスト$i$は,ツアー$i$に参加します。しかしツーリストたちはVIPなので,彼らは各ツアーの途中に1回だけ,ツーリストチケットを使うことで,好きな道の移動距離を$0$にすることができます。ツアーを通して ある道の距離を$0$にできるわけではないことに注意してください。
 すべての$i\ (1\le i \le N)$について,ツーリスト$i$の最短の移動距離を求めてください。

注意

 入出力が多いため,時間制限に注意して下さい。Python使いの人はPyPy3で提出してください。PyPy3ではACを確認しています。

入力

$N\ M$
$a_1\ b_1\ c_1$
$\vdots$
$a_{M}\ b_{M}\ c_{M}$

$2\le N \le 10^5$
$N-1\le M \le \min (2\times 10^5,N(N-1)/2)$
$1\le a_i,b_i \le N$
$1\le c_i \le 10^9$
$i\neq j$のとき$(a_i,b_i)\neq (a_j,b_j)$かつ$(a_i,b_i)\neq (b_j,a_j)$
与えらえるグラフは連結である。
与えられる入力はすべて整数である。

出力

$N$行出力してください。$i$行目には,ツーリスト$i$の最短の移動距離を出力してください。最後に改行してください。

サンプル

サンプル1
入力
5 6
1 2 2
1 3 3
1 4 4
2 5 10
3 5 7
4 5 8
出力
0
2
3
4
12

例えば,ツーリスト5は1→3→5と移動した後,ツーリストチケットを使って2に移動し,2→1と移動すると,移動距離は12となり,これが最短となります。

サンプル2
入力
6 8
1 2 5
2 6 8
1 3 3
3 5 2
5 6 1
1 4 6
4 5 2
1 6 10
出力
0
5
3
6
6
6

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。