题目描述

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

输入格式

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

下接 $M$ 行，每行三个整数 $u,v,w$，表示一条无向边 $u\leftrightarrow 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\le N\le10^4$，$1\le Q\le10^4$。