时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出 \(N\) 个顶点，\(M\) 条无向带权边的连通图，然后有 \(Q\) 次查询，每次查询图中某两点的最短路径长度。

【输入格式】

　　第一行：\(N,M,Q\)。
　　接下来 \(M\) 行，每行三个整数：\(x,y,t\)（\(1≤x,y≤N\)），表示顶点 \(x\) 与 \(y\) 有边，边权为 \(t\)。
　　再接下来 \(Q\) 行，每行两个整数 \(i,j(1≤i,j≤N)\)，表示要查询顶点 \(i\) 到顶点 \(j\) 的最短路径。

【输出格式】

　　包含 \(Q\) 行，对应输入数据中的查询。

【输入输出样例】

　Input

6 8 2
1 6 1
6 5 1
1 2 9
4 6 3
5 2 7
5 3 4
2 3 1
4 3 3
1 2
6 2

　Output

7
6

【数据限制】

　　\(100\%\) 的数据满足，\(0 < N ≤ 400\)，\(0 < M ≤ 10000\)，\(0<t≤1000000\)，\(q≤100\)。

【来源】

　　Mr.he