题目描述

给一个 N 个点 M 条边的连通无向图，满足每条边最多属于一个环，有 Q 组询问，每次询问两点之间的最短路径。

输入格式

输入的第一行包含三个整数，分别表示 N 和 M 和 Q。

下接 M 行，每行三个整数 u,v,w，表示一条无向边 u↔v，长度为 w。

最后 Q 行，每行两个整数 u,v，表示一组询问。

输出格式

输出 Q 行，每行一个整数表示询问的答案。

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

数据规模与约定

对于 100% 的数据，1≤N≤104，1≤Q≤104。