#P2125. 最短路
最短路
题目描述
给定一张有 个点、 条边的无向连通图,每条边至多属于一个简单环。对每组询问,求给定两点之间的最短路长度。
输入格式
第一行包含三个整数 。
接下来 行,每行三个整数 ,表示点 、 之间有一条长度为 的无向边。
接下来 行,每行两个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,表示对应的最短路长度。若两个端点相同,输出 。
数据范围
,,各点编号为 。本站评测数据的边权均满足 。
样例
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
5
6