頂点 辺の単純かつ連結な無向グラフが与えられます。 このグラフの 番目の辺は頂点 と頂点 を相互に結び、長さは です。
このグラフ上の最短路クエリが 個与えられるので、これに答えてください。 番目のクエリでは頂点 と頂点 の間の最短路を求めてください。
行出力してください。 について、 行目には 番目のクエリに対する答えを出力してください。
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