G: 旅費支給 - Travel Support -

物語

私，香坂穂乃果16歳！学生アイドルをやっています！！

学生アイドルの良さをみんなに伝えるためのライブをやろうと，たくさんの学生アイドルの人たちを呼んでアキバスタジアムでライブをします．

だけど，遠くから来るライブ参加者もいてとっても電車賃がかかるの．だからu’sのメンバーでバイトをして，ライブ参加者たちに電車賃を渡すことにしたんだ！ただ，バイト代が入るのが遅いから電車賃を渡すのがライブ参加者の出発に間に合わないことがあったり，バイト代が足りなくて電車賃の全額は渡せないことがあるんだ．そんな時は，ライブ参加者に足りない分のお金を事前に用意してもらうのだけど，どのくらい用意して貰えばいいんだろう？

そこで，あなたにライブ参加者が用意する必要のある最小の金額を求めて欲しいんだ！

おねがい真衣ちゃん，電車賃貸して？

問題

N個の都市があり，それぞれ1〜Nまでの番号がつけられている．i（1 ≤ i ≤ N）番目の都市は人口がt_i（i ≠ jならばt_i ≠ t_j）である．

現在，都市1にK人のライブ参加者が集まろうとしている．許された交通手段がM通りあり，i番目の交通手段では都市a_iと都市b_i（1 ≤ a_i, b_i ≤ N）をc_i円の費用で双方向に移動ができる．移動にはどの交通手段でも1日を必要とする．

i（1 ≤ i ≤ K）番目の参加者は，都市x_iを出発し必要な費用が最小になるような経路で都市1に向かう．費用が最小な経路が複数ある場合は，移動日数が少ない経路を選ぶ．それでも複数の経路がある場合は，人口が少ない都市へ優先して移動するような経路を選ぶ．これにより経路が定まり到着するまでの日数がわかるので，参加者はそれぞれライブが行われる日にちょうど都市1に到着するように移動を開始する．

また，i（1 ≤ i ≤ K）番目の参加者にはライブのd_i日前にp_i円の支給がある事が知らされている．支給後の移動には可能なかぎり支給された費用を用いるが，支給前にかかっている費用や，賄いきれない支給後の費用は，各参加者が事前に用意する必要がある．

それぞれの参加者が事前に用意する費用の最小値を求めよ．

入力形式

入力は次の形式で与えられる．

N M
t_1 ... t_N
a_1 b_1 c_1
...
a_M b_M c_M
K
x_1 d_1 p_1
...
x_K d_K p_K

1行目には2つの整数N（1 ≤ N ≤ 100,000），M（0 ≤ M ≤ 500,000）が空白区切りで与えられ，それぞれ都市数と許された交通手段の数を表す．2行目にはN個の整数t_i（1 ≤ i ≤ N，1 ≤ t_i ≤ 500,000）が空白区切りで与えられる．t_iは都市iの人口を表し，i ≠ jならばt_i ≠ t_jを満たす．

続くM行は交通手段についての入力であり，i番目の交通手段について3つの整数a_i，b_i，c_iが空白区切りで与えられる．これは，i番目の交通手段で都市a_iとb_i（1 ≤ a_i, b_i ≤ N, a_i ≠ b_i）を行き来でき，c_i（1 ≤ c_i ≤ 10,000）円の費用がかかることを表す．また，任意の2つの都市を直接結ぶ2つ以上の交通手段は無い．全ての都市は，いくつかの交通手段を用いて互いに行き来できる．

次の行には参加者の人数を表す整数K（1 ≤ K ≤ 100,000）が与えられる．

続くK行は参加者たちについての入力であり，i番目の参加者について3つの整数x_i, d_i, p_iが空白区切りで与えられる．これは，i番目の参加者が最初は都市x_i（1 ≤ x_i ≤ N）におり，ライブのd_i（0 ≤ d_i ≤ 100,000）日前にp_i（0 ≤ p_i ≤ 100,000）円の支給を受けることを表す．

出力形式

それぞれの参加者が事前に用意する費用の最小値を，1番目の参加者から順に改行区切りで出力せよ．

入出力が非常に大きくなる可能性があるので，入出力の関数には高速なものを用いることを推奨する．

入力例1

5 6
100 80 70 60 50
1 2 500
2 5 100
1 3 400
1 4 200
3 5 700
4 5 800
1
5 3 600

出力例1

0

移動全体にかかる費用の最小値は600円で，2日間で都市1につくことができる．3日前に十分な費用が支給されるので，事前に費用を用意する必要はない．

入力例2

5 6
400 200 500 300 100
1 2 500
2 5 100
1 3 400
1 4 200
3 5 200
4 5 800
1
5 1 800

出力例2

100

費用が最小でありかつ日数が最小となる経路は5−2−1と5−3−1の2つの経路があるが，都市5から次の都市へ移動する際に，都市3より都市2の方が人口が少ないので経路5−2−1を選ぶ．合計の費用は600円なの支給額で全額支払い可能であるが，支給されるより前の費用は立て替えなければならないので，5−2間の費用である100円だけ事前に用意する必要がある．

入力例3

10 13
100 90 80 70 60 50 40 30 20 10
1 2 5
1 4 4
2 3 3
3 5 2
4 5 6
4 6 7
4 7 2
5 8 1
5 9 8
6 7 10
6 9 7
6 10 3
7 10 10
10
2 0 0
2 1 3
3 0 100000
3 1 3
3 1 100000
3 2 100000
3 100000 100000
8 1 5
9 2 11
10 0 0

出力例3

5
2
8
5
3
0
0
7
7
14