住在南山校区的HY喜欢散步。他发现南山校区有n个景点（从1到n进行编号）很值得观赏，比如竹林舞步，小河夕阳等。这些景点中，有些相互能够直达，而有些要先经过其他的一些景点才能到达。他已经记下了一些直达道路的用时信息。散步是好的，但散步太久也会累的，所以当他身处某个景点时，就想知道从这个景点散步到另一个他想去的景点的最少用时。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。
每组测试包含两个部分。分别是： 景点信息 和 查询。

景点信息 部分,首先是2个整数n和m（2≤n≤100，1≤m≤n(n-1)/2），分别表示有n个景点，以及m条直达道路的用时信息。然后有m行输入，每行输入三个整数a,b,c（1≤a,b≤n，a≠b，1≤c<100），表示由景点a散步到景点b，HY散步需要用时c分钟，当然，他由景点b散步到景点a也要c分钟。

查询 部分，首先是1个整数k（1<=k<=5000），表示后面接k次询问。紧接着k行数据，每行包括两个整数s,d（1≤s，d≤n，s≠d），分别表示HY想知道从景点s散步到另一个景点d的用时（分钟数）。

注意，因为HY有点粗心，可能发生以下情况：
（1）他所记下有些用时信息可能重复，比如：
1 2 3
2 1 3
（2）有些同一条路的用时信息可能不一致，比如