#P2125. 最短路

最短路

题目描述

给定一张有 NN 个点、MM 条边的无向连通图,每条边至多属于一个简单环。对每组询问,求给定两点之间的最短路长度。

输入格式

第一行包含三个整数 N,M,QN,M,Q。

接下来 MM 行,每行三个整数 u,v,wu,v,w,表示点 uu、vv 之间有一条长度为 ww 的无向边。

接下来 QQ 行,每行两个整数 u,vu,v,表示一次询问。

输出格式

输出 QQ 行,每行一个整数,表示对应的最短路长度。若两个端点相同,输出 00。

数据范围

1≤N,Q≤1041\le N,Q\le10^4,0≤M≤2×1040\le M\le2\times10^4,各点编号为 1∼N1\sim N。本站评测数据的边权均满足 1≤w≤10001\le w\le1000。

样例

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