D - Shortest Paths on Unicyclic Graph

頂点 辺の単純かつ連結な無向グラフが与えられます。 このグラフの 番目の辺は頂点 と頂点 を相互に結び、長さは です。

このグラフ上の最短路クエリが 個与えられるので、これに答えてください。 番目のクエリでは頂点 と頂点 の間の最短路を求めてください。

• 入力はすべて整数である

行出力してください。 について、 行目には 番目のクエリに対する答えを出力してください。

4 3
1 2 1
1 3 2
3 4 4
4 1 8
1 2
1 4
4 2

1
6
7

11 6
1 5 1
7 5 2
1 7 4
2 1 8
2 4 16
3 2 32
5 6 64
8 7 128
9 7 256
9 10 512
11 9 1024
1 7
3 6
11 8
11 10
4 10
6 9

3
105
1408
1536
795
322

10 10
10 7 508252356070
10 4 328974562802
9 1 885368849936
9 10 580933898755
9 5 349344869736
1 6 394235217277
10 3 21578149681
1 2 19279158318
6 4 803839369377
9 8 982198770298
1 6
8 2
1 4
1 7
7 6
6 10
5 7
4 3
10 2
4 8

394235217277
1886846778552
1198074586654
1974555104761
1641066288249
1132813932179
1438531124561
350552712483
1485581907009
1892107231855