1110 - 我々はどこから来たのか 我々は何者か 我々はどこへ行くのか
問題
情報処理部全員で合宿を行うことになりました。
今日は私たちが待ちに待った合宿当日です。
移動も順調に終わったかのように思えましたがそんなことはありませんでした。
駅からホテルに向かおうとしたところ、意識を失ってしまいました。
M分が経ったころでしょうか、幸い私たちは意識を取り戻しました。
しかし、困ってしまうことが起きました。
皆の記憶がはっきりしないのです。
私たちがどこから来たのか、私たちは何者なのか、私たちはどこへ行こうとしていたのか。
全く思い出すことができません。
ぼんやりと覚えているのは自分たちが仲間であることと、どこかへ向かっている最中であるということです。
持ち物やiPhoneなどを確認したところ、どうやら私たちはホテルへ行く途中だったようです。
そこで、目的地に向かえば記憶を取り戻すことができるかもしれないと考えた私たちは、とりあえずホテルへ向かうことにしました。
どうやら駅からホテルへはバスなどを乗り継いで行く必要があるようです。
時刻表や地図を確認したところ、バス停からバス停までの移動時間と、そのバス停で待つ必要がある時間をすべて知ることができました。
どうやらバス停はS1からSNまであるみたいです。なお、S1は私たちがいる駅、SNは目的地にそれぞれあるバス停です。
可能な限り早くホテルに行こうとするとき、何分かかるでしょうか。
計算しましょう。
入力
N M W1 ...... WN s1 t1 c1 ...... sM tM cM
バス停の数Nと移動手段の数Mが与えられます。
その後N行に各バス停で待つ必要のある時間Wが与えられます。
その後M行に渡ってバス停の番号s, tと自然数cが与えられます。
これはバス停sからバス停tに行く時、cの移動時間がかかることを意味します。なお、一方通行であることに注意してください。
出力
min_cost
駅からホテルに行った時の最短時間を求めてください。
ただし、どのようにしてもホテルへたどり着けないことがあります。
その場合はWhodunitと出力してください。
制約
$3$ ≤ $N$ ≤ $10$4$4$ ≤ $M$ ≤ min(N*(N-1), $10$5)
$1$ ≤ $s$, $t$ ≤ $N$
$0$ ≤ $W$, $c$ ≤ $10$7
テストケース
例1
入力
6 9 0 0 0 0 0 0 1 2 2 1 3 5 1 4 4 2 4 3 3 4 2 2 5 6 4 5 2 3 6 6 5 6 4
出力
10
バス停での待ち時間はありません。
例2
入力
6 9 2 3 5 7 11 13 1 2 2 1 3 5 1 4 4 2 4 3 3 4 2 2 5 6 4 5 2 3 6 6 5 6 4
出力
18