Một tỉnh có ~n~ địa điểm và ~m~ tuyến đường hai chiều. Từ mọi địa điểm đều có thể đi đến mọi địa điểm khác. Mỗi tuyến nối hai địa điểm và có chi phí duy trì ~w~. Đơn vị quản lý nhận ~q~ yêu cầu, mỗi yêu cầu nêu hai địa điểm ~u, v~.

Với mỗi yêu cầu, hãy tính tổng chi phí duy trì của những tuyến đường không thể thay thế là tuyến đường xuất hiện trong mọi cách đi từ ~u~ đến ~v~. Tương đương, một tuyến được tính nếu tạm đóng riêng tuyến đó thì không còn cách nào đi từ ~u~ đến ~v~.

Input

• Dòng đầu chứa ~n, m, q~ ~(1 \le n, q \le 200000; n-1 \le m \le 300000)~;

• ~m~ dòng tiếp theo, mỗi dòng chứa ~u, v, w~ mô tả một tuyến đường hai chiều ~(1 \le u, v \le n; u \ne v; 1 \le w \le 10^9)~;

• ~q~ dòng tiếp theo, mỗi dòng chứa ~u, v~ mô tả một yêu cầu ~(1 \le u, v \le n)~.

Mạng lưới liên thông; có thể có nhiều tuyến nối cùng một cặp địa điểm.

Output

• Với mỗi yêu cầu, in tổng chi phí của các tuyến không thể thay thế. Nếu không có tuyến nào như vậy thì in ~0~;

• Trong một yêu cầu, ~u~ và ~v~ có thể trùng nhau; khi đó kết quả bằng ~0~.

Scoring

Sample Input 1

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

Sample Output 1

0
5
12
7

Notes

Các địa điểm ~1, 2, 3~ có nhiều cách đi thay thế lẫn nhau; ~4, 5, 6~ cũng vậy. Mọi cách đi giữa hai nhóm này phải qua tuyến ~3-4~ có chi phí duy trì ~5~; muốn tới địa điểm ~7~ còn phải qua tuyến ~6-7~ có chi phí duy trì ~7~. Vì thế bốn kết quả lần lượt là ~0, 5, 12~ và ~7~.