As Soon As Possible 2

2 secs 1024 MB
magurofly

問題文


アナウンス


  • 制約が間違っていたため修正しました。 ではなく です。
  • 5/1 14:56: サンプルと制約を修正しました。 になりました。

ストーリー


就職のために上京した高橋くんは、部屋を探しています。

高橋くんは時間を有効に使いたいため、通勤にかかる時間を計算してみることにしました。

問題


高橋くんの街には 個の地点と 本の一方通行の道路があり、部屋の候補は 個あります。

番目の道路は地点 から へ行くことができ、通るとき の時間がかかります。

番目の部屋の候補は地点 にあります。

となる に対し、 番目の部屋の候補と地点 にある職場との往復にかかる時間を求めてください。

なお、職場との往復にかかる時間とは、職場にいる時間を無視したときの、家から職場へ行き、職場から家まで帰るのに必要な時間を指します。

制約


  • どの地点からも 本以上の道路を使うことで別の地点に行くことができる
  • 入力は全て整数である

入力


出力


行出力せよ。

入出力例


入力例1
6 7 4
5 2 1
6 3 3
1 6 5
1 5 8
4 1 9
3 4 1
2 3 6
2 6 5 3
出力例1
25
18
25
18

地点 からの往復経路は となり、かかる時間は です。

地点 からの往復経路は となり、かかる時間は です。

地点 からの往復経路は となり、かかる時間は です。

地点 からの往復経路は となり、かかる時間は です。

入力例2
2 2 2
1 2 2
2 1 2
1 2
出力例2
0
4

社宅がある場合もあります。

入力例3
5 5 1
1 2 900000000
2 3 900000000
3 4 900000000
4 5 900000000
5 1 900000000
2
出力例3
4500000000

入出力は ビット整数で表せる範囲を超えることがあります。

入力例のグラフ

Submit


Go (1.14)