問題

ahri と teemo がうしたぷにきあ王国で観光をします。うしたぷにきあ王国には$N$個の都市と$M$本の道があり、任意の都市は何本かの道を通って必ず到達することができます。 また、$i$番目の道を使うと都市$a_i$と都市$b_i$を距離$d_i$で行き来することができて、王国に閉路はありません。 ahri は都市$X$からスタートして都市$Z$に向かって最短経路で観光をし、 teemo は都市$Y$からスタートして都市$Z$に向かって最短経路で観光をします。

ahri と teemo は最初1人旅ですが、途中ある都市で偶然出会った時は出会った都市から都市$Z$まで2人旅で一緒に最短経路で観光します。

ahri と teemo のスタート地点となる都市の組$(X,Y)$のクエリが$Q$個与えられます。各クエリに対し、2人旅で移動する可能性のある距離のうち最大値を改行区切りで出力してください。

制約

$2 \leq N \leq 10^5$

$N-1 \leq M \leq 10^5$

$1 \leq a_i,b_i \leq N, \ a_i \neq b_i$

$1 \leq d_i \leq 10^{9}$

$1 \leq Q \leq 10^5$

$1 \leq Z \leq N$

$1 \leq X_i,Y_i \leq N, \ X_i \neq Y_i$

入力

$N \ M$

$a_1 \ b_1 \ d_1$

︙

$a_{M} \ b_{M} \ d_{M}$

$Q \ Z$

$X_1 \ Y_1$

︙

$X_{Q} \ Y_{Q}$

出力

各クエリに対し、2人旅で移動する可能性のある距離のうち最大値を改行区切りで出力してください。

サンプル

8 8
8 6 1
7 6 2
6 5 2
6 5 3
5 4 4
5 3 5
5 2 5
2 1 6
2 8
1 3
1 2

3
8

クエリ1では

ahri は 1→2→5→6→8 teemo は 3→5→6→8 の順番で都市を観光します。

都市5で出会った時2人旅が最長になります。 ただし、2人旅でも最短経路を通って観光するので出力は都市5から都市8の距離3になります。

クエリ2では

ahri は 1→2→5→6→8 teemo は 2→5→6→8 の順番で都市を観光します。

都市2で出会った時2人旅が最長になるので、都市2から都市8の距離8を出力します。

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

0

クエリ1では ahri は 1→3→5 teemo は 4→5 の順番で都市を観光します。 都市5でしか出会えないので、2人旅の最長距離は0です。

9 18
1 4 52
4 5 64
3 5 85
1 2 41
6 8 65
1 7 83
5 8 99
1 9 51
1 4 16
6 8 37
1 4 67
3 5 50
6 8 31
4 5 45
3 5 66
1 7 17
1 9 38
3 5 42
3 3
1 8
2 7
3 6

42
103
0