测试数据来自 system/3097

作业已超过截止时间，您无法递交本题目。

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

---

【题目描述】

　　给出 \(N\) 个顶点（依次标号为 \(1..N\)），\(M\) 条无向带权边的连通图，然后有 \(Q\) 次查询，每次查询的参数为：\(i,j,k\)，表示从 \(i\) 到 \(j\) 中间只经过标号不大于 \(k\) 的点的最短路径长度。

【输入格式】

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

【输出格式】

　　包含 \(Q\) 行，对应输入数据中的查询，若不存在路径，则输出 None。

【输入输出样例】

　Input

5 6 3
1 2 12
1 3 5
2 3 8
2 4 8
2 5 3
3 4 4
3 4 1
1 2 4
5 1 2

　Output

4
12
15

【数据限制】

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

【来源】

　　Mr.he