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

---

【题目描述】

　　小H有 \(K\) 个好朋友，城市中有 \(N\) 个居民点，编号 \(1\sim N\)，有 \(M\) 条双向边，第 \(i\) 条边连接居民点 \(R_i\) 和 \(S_i\) ，该边的长度是 \(L_i\)。居住在居民点 \(P_i\) 的朋友A，它想送一份新年礼物给居住在居民点 \(Q_i\) 的朋友B，但是朋友A必须先到小H(居住在编号1的居民点)那里取礼物，然后再送给朋友B。

　　你的任务是：朋友 \(A\) 至少需要走多远的路程？

【输入格式】

　　第 \(1\) 行：三个整数：\(N,M,K\)。
　　第 \(2..M+1\) 行：每行三个整数：\(R_i,S_i\) 和 \(L_i\)，描述一条边的信息。
　　第 \(M+2..M+K+1\) 行：共 \(K\) 行，每行两个整数 \(P_i\) 和 \(Q_i\)，表示住在 \(P_i\) 居民点的朋友送礼物给住在 \(Q_i\) 居民点的朋友。

【输出格式】

　　共 \(K\) 行，每行一个整数，表示住在 \(P_i\) 居民点的朋友送礼给住在 \(Q_i\) 居民点的朋友至少需要走的路程。

【输入输出样例】

　Input

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

　Output

6
6
10

【数据限制】

　　\(100\%\) 的数据满足，\(1≤K≤25000\)，\(2*B≤N≤50000\)，\(N-1≤M≤100000\)，\(1≤L_i≤2000\)

【来源】

　　Mr.he