Trong một vương quốc kỳ diệu, các thành phố và con đường tạo thành một mạng lưới rộng lớn. Mỗi thành phố được đánh số từ ~1~ đến ~N~, được kết nối với nhau bằng ~M~ con đường hai chiều. Vương quốc này không chỉ nổi tiếng với cảnh quan tuyệt đẹp mà còn bởi sự phức tạp trong hệ thống giao thông.

Có ~N~ thành phố trong vương quốc, và giữa chúng tồn tại ~M~ con đường hai chiều. Mỗi con đường kết nối hai thành phố ~u~ và ~v~, khách lữ hành cần một khoảng thời gian nhất định (trọng số ~w~) để đi qua. Các con đường có thể có độ dài khác nhau, và không phải mọi cặp thành phố đều được nối trực tiếp.

Bạn là một nhà thám hiểm lừng danh, được giao nhiệm vụ trả lời ~Q~ câu hỏi từ những khách du hành khác. Mỗi câu hỏi đưa ra: "Đâu là con đường ngắn nhất từ thành phố ~x~ đến thành phố ~y~?"

Nhiệm vụ của bạn là xác định thời gian di chuyển ngắn nhất giữa hai thành phố bất kỳ. Nếu không tồn tại đường đi từ ~x~ đến ~y~, hãy báo rằng chuyến đi là không thể.

Input

• Dòng đầu tiên: ba số nguyên dương ~N, M, Q~.

  • ~N~: số thành phố ~(N \leq 500)~.
  • ~M~: số con đường ~(M \leq 10{,}000)~.
  • ~Q~: số lượng truy vấn ~(Q \leq 10{,}000)~.

• ~M~ dòng tiếp theo: mỗi dòng chứa ba số nguyên dương ~u, v, w~.

  • ~u, v~: hai thành phố được kết nối bởi một con đường ~(u, v \leq N)~
  • ~w~: thời gian di chuyển trên con đường này ~(w \leq 10^9)~
• ~Q~ dòng cuối: mỗi dòng chứa hai số nguyên ~x, y~ – biểu thị một truy vấn hỏi đường đi ngắn nhất từ thành phố ~x~ đến thành phố ~y~.

Output

• Với mỗi truy vấn, in ra một dòng chứa: Thời gian di chuyển ngắn nhất từ ~x~ đến ~y~, hoặc -1 nếu không tồn tại đường đi.

Sample Input

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

Sample Output

5
5
8
-1
3