题目描述
采蘑菇的小西佬进入了一个地下迷宫，这个地下迷宫有n个房间，有m条通道，每条通道连接着两个房间，每次通过一个通道都需要花费时间，假设他现在在第j个房间，他想知道前往第k个房间最少需要多少时间。（保证任意两个房间都可以互相到达）
输入
第一行输入两个数n,m(n，m<=1e5,m<=n+10);
接下来m行每行输入三个数，u,v,t，表示该通道连接第u和第v个房间，且通过时间为t;
接下来输入一个询问次数q(q<=1e5);
接下里q行，每行输入两个数j,k,
输出
对于每个询问，输出第j到第k个房间所需要的最少时间。
样例输入
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
样例输出
3
4
1
提示
浙江理工大学月赛2019年5月
来源/分类
浙江理工大学月赛