As Soon As Possible 2

2 secs 1024 MB
magurofly's icon magurofly

問題文

アナウンス

  • 制約が間違っていたため修正しました。 Ci109C_i \le 10^9 ではなく Ci1018C_i \le 10^{18} です。
  • 5/1 14:56: サンプルと制約を修正しました。 Ci109C_i \le 10^9 になりました。

ストーリー

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

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

問題

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

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

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

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

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

制約

  • 1N,Q1051 \le N, Q \le 10^5
  • NMmin(N(N1),105)N \le M \le \min(N(N-1), 10^5)
  • 1Ai,Bi,HjN1 \le A_i, B_i, H_j \le N
  • 1Ci1091 \le C_i \le 10^9
  • どの地点からも 11 本以上の道路を使うことで別の地点に行くことができる
  • 入力は全て整数である

入力

N M QA1 B1 C1AM BM CMH1  HQN\ M\ Q\\ A_1\ B_1\ C_1\\ \vdots\\ A_M\ B_M\ C_M\\ H_1\ \ldots\ H_Q

出力

QQ 行出力せよ。

入出力例

入力例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

地点 22 からの往復経路は 2341522\to3\to4\to1\to5\to2 となり、かかる時間は 2525 です。

地点 66 からの往復経路は 634156\to3\to4\to1\to5 となり、かかる時間は 1818 です。

地点 55 からの往復経路は 5234155\to2\to3\to4\to1\to5 となり、かかる時間は 2525 です。

地点 33 からの往復経路は 341633\to4\to1\to6\to3 となり、かかる時間は 1818 です。

入力例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

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

入力例のグラフ

提出


Go (1.21)