0871 - 移動(隠密行動)

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1620 / x 9 / 統計 /


TLE
1sec
MLE
64MB
得点
1

問題

あらゆる種族が「星杯」をかけて争った、「大戦」中のある日・・・
リク「この作戦を成功させるために、 l 個のグループが最短でどれぐらいの時間で町 s から町 g までたどり着けるかが知りたいんだが、求められるか?」
あなたはリクからいくつかの情報をもらった。まず 1 から n までの番号がふられた n 個の町の、その町を出るのにかかる時間 k と、 m 本の町をつなぐルートとそこを通るのにかかる時間 c 、そして l 個のグループの出発地点と目的地を町の番号で表した sg だ。
あなたには、これらの情報を元にそれぞれのグループが出発地点から目的地まで最短でどのくらいの時間でたどり着けるかをリクに教えてもらいたい。


「さあ、ゲームを始めよう」

入力

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 行につながっている町を表す整数 ab と、そこを通るのにかかる時間を表す整数 c が与えられる。

出力

それぞれのグループの目的地にたどり着くのにかかる最短の時間を改行区切りで出力せよ。もし、目的地にたどり着けない場合は"we can't."と出力せよ。出力の最後に改行を入れることを忘れずに。

制約

全ての入出力ケースについて以下を満たす。

  • 2 ≦ n ≦ 10000
  • 0 ≦ m ≦ min(n(n-1)/2,10000)
  • 1 ≦ l ≦ 100
  • 0 ≦ k ≦ 10000
  • 1 ≦ s, gn
  • 1 ≦ a, bn
  • 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.