Mô tả bài toán: Tìm đường đi ngắn nhất giữa các thành phố

Có n thành phố và m con đường giữa chúng. Nhiệm vụ của bạn là xử lý q truy vấn để xác định độ dài của đường đi ngắn nhất giữa hai thành phố được cho trước.

Input:

• Dòng đầu tiên chứa ba số nguyên n, m, và q: số lượng thành phố, số lượng con đường, và số lượng truy vấn.
• Tiếp theo có m dòng, mỗi dòng chứa ba số nguyên a, b, và c:
  • ~a~: thành phố đầu của con đường.
  • ~b~: thành phố cuối của con đường.
  • ~c~: độ dài của con đường nối ~a~ và ~b~.
• Cuối cùng, có q dòng, mỗi dòng chứa hai số nguyên a và b, yêu cầu tìm đường đi ngắn nhất giữa thành phố ~a~ và ~b~.

Mỗi con đường là hai chiều.

Output:

• Đối với mỗi truy vấn, in ra độ dài của đường đi ngắn nhất giữa ~a~ và ~b~.
• Nếu không tồn tại đường đi, in ra ~-1~.

Ràng buộc:

• ~1 \leq n \leq 500~
• ~1 \leq m \leq n^2~
• ~1 \leq q \leq 10^5~
• ~1 \leq a, b \leq n~
• ~1 \leq c \leq 10^9~

Ví dụ:

Input:

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

Output:

5
5
8
-1
3