Background

瑞文戴尔有n个亭子，编号为1~n，每两个亭子之间可能有一条或多条路，并已知这m条路的长度。现有Q次询问，询问给出两个亭子编号u,v，求从u到v最短路的长度。 PS.两个亭子之间直接连通的路不一定是最短的路。

Format

Input

输入第一行给出两个整数n,m，(2<=n<=200, m<=nn) 接下来m行，每行三个整数a,b,w，表示a到b之间有一条长度为w的通路（双向的）。 接下来一行为一个整数Q，表示接下来有Q次查询，Q<=nn/2。 接下来Q行，每行两个整数u,v，表示查询从u到v的最短距离

当m和n都为0时输入结束。

对于每个查询，输出u到v之间的最短距离。

Samples

3 3
1 2 100
1 3 300
2 3 50
2
2 1
1 3
0 0

100
150

Limitation

1s, 1024KiB for each test case.