最短路
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在n个城市中修建有m段的双向铁路，每段铁路是连接于两个城市的，都有一个长度，且从任何城市出发可以直接或者间接到达其他任何的城市。
现在小明想从某个城市出发到达某个城市（可能是同一城市），需要你为他选择一条路径。
但是由于小明晕车，小明只希望自己乘坐的若干段铁路中最长的长度可以尽量最小（也就是路径长度不再为每段铁路长度之和，而是路径中某段最长的铁路长度）。
求从某城市出发到指定城市的最短路径距离。

注意：所给铁路可能有重边（也就是输入可能存在两顶点相同的边，距离可能不一样）

输入描述:

第一行两个整数
第2到m+1行，每行三个整数x，y，z，分别表示x城市到y城市中有一个双向的铁路，长度为z
第m+2行一个整数q，表示询问q次
第m+3到m+q+2行，每行有两个整数L，R，表示询问从 L 到 R 的最短路径距离

输出描述:

输出共q行，每行一个整数表示从起点城市到终点城市的最短距离
示例1

输入

复制 
4 4
1 2 10
1 3 1
2 3 1
2 4 1
4
1 1
1 2
1 3
1 4

输出

复制 
0
1
1
1
示例2

输入

复制 
3 3
1 2 1
2 3 100
1 3 2
1
1 3

输出

复制 
2

备注:

对于样例一

1到1的最短距离是0
1到3的最短距离是1
1到2的最短距离是1（1先到3，再到2，其中最长的铁路长为1）
1到4的最短距离是1（1先到3，再到2，再到4，其中最长的铁路长为1）