题目描述

在某个遥远的国家里，有$n$个城市,编号分别为$1，2，3，...，n$。这个国家的政府修建了$m$条双向道路，每条道路连接着两个城市。政府规定从城市$S$到城市$T$需要收取的过路费为所经过城市之间道路长度的最大值。如：$A$到$B$长度为$2$，$B$到$C$长度为$3$，那么开车从$A$经过$B$到$C$需要上交的过路费为$3$。 佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据佳佳开车的起止城市，提供给他从开始城市到达目标城市，最少需要上交多少过路费。

输入

第一行是两个整数$n$ 和$m$，分别表示城市的个数以及道路的条数。 接下来$m$行，每行包含三个整数 $a，b，w（1≤a，b≤n，0≤w≤10^9）$，表示$a$与$b$之间有一条长度为$w$的道路。 接着有一行为一个整数$q$，表示佳佳发出的询问个数。 再接下来$q$行，每一行包含两个整数$S，T（1≤S,T≤n）$, 表示开始城市$S$和目标城市$T$。

输出

输出文件共$q$行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。

输入样例

4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1

输出样例

20
20

提示

【数据规模】 对于30%的数据，满足$1≤ n≤1000，1≤m≤10000，1≤q≤100$。 对于50%的数据，满足$1≤n≤10000，1≤m≤10000，1≤q≤10000$。 对于100%的数据，满足$1≤n≤10000，1≤m≤100000，1≤q≤10000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。