当前没有测试数据。

题目描述

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

PS. 两个亭子之间直接连通的路不一定是最短的路。

输入格式

本题有多组数据。对于每组数据：

输入第一行给出两个整数 n,m(2≤n≤200,m≤$n^2$)。

接下来 m 行，每行三个整数 a,b,w，表示 a 到 b 之间有一条长度为 w 的通路（双向的）。

接下来一行为一个整数 Q，表示接下来有 Q 次查询，Q≤$n^2/2$。

接下来 Q 行，每行两个整数 u,v，表示查询从 u 到 v 的最短距离。

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

输出格式

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

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

100
150