問題文

アナウンス

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

ストーリー

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

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

問題

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

$i$ 番目の道路は地点 $A_i$ から $B_i$ へ行くことができ、通るとき $C_i$ の時間がかかります。

$j$ 番目の部屋の候補は地点 $H_j$ にあります。

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

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

制約

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

入力

出力

$Q$ 行出力せよ。

入出力例

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

25
18
25
18

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

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

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

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

2 2 2
1 2 2
2 1 2
1 2

0
4

社宅がある場合もあります。

5 5 1
1 2 900000000
2 3 900000000
3 4 900000000
4 5 900000000
5 1 900000000
2

4500000000

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