Sau bao nhiêu ngày tháng xây dựng ở vùng đất mới, thì CJ đã cử vài lực lượng cùng anh tới khu vực đó để khảo sát tình hình làm việc cũng như địa thế. CJ đặt biệt quan tâm đến sức mạnh và sự hỗ trợ của đồng đội, nên đã khảo sát như sau:

• Ở vùng đó có \(N\) căn cứ, được đánh số từ 1 tới \(N\) và \(M\) tuyến đường hai chiều, được đánh số từ \(1\) tới \(M\).
• Lực lượng của CJ sẽ tìm độ dài đường đi ngắn giữa Q cặp căn cứ \(s\), \(t\) bất kì do CJ muốn xem xét để làm kết quả của cuộc khảo sát, rồi sau đó về họp bàn sau.
• Định nghĩa căn cứ \(s\) có thể đi tới căn cứ \(t\) là tồn tại một đường đi từ \(s\) tới \(t\), tức là tồn tại dãy các căn cứ \(P=⟨s=p_0,p_1,...,p_k=t⟩\) sao cho \(\forall i:1 \leq i \leq k\) thì tồn tại tuyến đường trực tiếp giữa hai căn tứ \(p_{i-1}\) và căn cứ \(p_i\).

Yêu cầu: Với mỗi cặp căn cứ \(s\), \(t\) do CJ chọn, tìm đường đi ngắn nhất giữa hai căn cứ \(s\) và \(t\).

Input

• Gồm \(M + Q + 1\) dòng:

• Dòng thứ nhất chứa ba số nguyên dương \(N\), \(M\), \(Q\) thể hiện số căn cứ, số con đường và số cặp căn cứ muốn xem xét.

• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_i\), \(v_i\) và \(c_i\) thể hiện có tuyến đường nối trực tiếp giữa \(u_i\) và \(v_i\) và có độ dài là \(c_i\) \((c_i \leq 10^9, u_i \neq v_i)\).
• \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa hai số \(s_i\) và \(t_i\) thể hiện cặp căn cứ \(s_i\), \(t_i\) mà CJ muốn xem xét \((s_i \neq t_i)\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) là đường đi ngắn nhất giữa cặp căn cứ \(s_i\), \(t_i\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^2, M \leq 10^3, Q \leq 5 \times 10^2\).
• Subtask \(2\) (\(25\%\) số điểm): \(N \leq 3 \times 10^2, M \leq 2 \times 10^4, Q \leq 2 \times 10^2\).
• Subtask \(3\) (\(50\%\) số điểm): \(N \leq 4 \times 10^2, M \leq 35 \times 10^3, Q \leq 35 \times 10^3\).

Example

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

10
7