問題
あらゆる種族が「星杯」をかけて争った、「大戦」中のある日・・・
リク「この作戦を成功させるために、 l 個のグループが最短でどれぐらいの時間で町 s から町 g までたどり着けるかが知りたいんだが、求められるか？」
あなたはリクからいくつかの情報をもらった。まず 1 から n までの番号がふられた n 個の町の、その町を出るのにかかる時間 k と、 m 本の町をつなぐルートとそこを通るのにかかる時間 c 、そして l 個のグループの出発地点と目的地を町の番号で表した s と g だ。
あなたには、これらの情報を元にそれぞれのグループが出発地点から目的地まで最短でどのくらいの時間でたどり着けるかをリクに教えてもらいたい。
「さあ、ゲームを始めよう」
入力
n m l k0 : : : kn-1 s0 g0 : : : sl-1 gl-1 a0 b0 c0 : : : am-1 bm-1 cm-1
1 行目に町の数を表す整数 n と、道の数を表す整数 m 、グループの数を表す整数 l が与えられる。
続く n 行に町i を出るのにかかる時間を表す整数 k が与えられる。
続く l 行にグループi の出発地点を表す整数 s 、目的地を表す整数 g が与えられる。
続く m 行につながっている町を表す整数 a 、 b と、そこを通るのにかかる時間を表す整数 c が与えられる。
出力
それぞれのグループの目的地にたどり着くのにかかる最短の時間を改行区切りで出力せよ。もし、目的地にたどり着けない場合は"we can't."と出力せよ。出力の最後に改行を入れることを忘れずに。
制約
全ての入出力ケースについて以下を満たす。
- 2 ≦ n ≦ 10000
- 0 ≦ m ≦ min(n(n-1)/2,10000)
- 1 ≦ l ≦ 100
- 0 ≦ k ≦ 10000
- 1 ≦ s, g ≦ n
- 1 ≦ a, b ≦ n
- 1 ≦ c ≦ 10000
入出力例
入力例1
2 1 2 1 5 1 2 2 1 1 2 5
出力例1
6 10
入力例2
10 4 5 0 5 5 80 15 50 10 60 15 5 1 2 1 5 4 3 5 10 7 8 1 2 5 2 5 5 5 10 5 1 10 100
出力例2
5 15 we can't. 20 we can't.