Đường đi ngắn nhất II

Trong quá trình quy hoạch một khu đô thị mới, FullHouse Dev được giao nhiệm vụ tính toán các tuyến đường ngắn nhất giữa các khu vực.

Bài toán

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

INPUT FORMAT:

• 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.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): có một con đường hai chiều giữa thành phố \(a\) và thành phố \(b\) với độ dài \(c\).
• \(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(a\) và \(b\): yêu cầu tìm độ dài đường đi ngắn nhất giữa thành phố \(a\) và thành phố \(b\).

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra độ dài của đường đi ngắn nhất. 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

Giải thích:

• Với truy vấn 1 và 2: Đường đi ngắn nhất giữa thành phố 1 và 2 (hoặc ngược lại) có độ dài 5.
• Với truy vấn 3: Đường đi ngắn nhất từ 1 đến 3 có độ dài 8 (đi từ 1 → 2 → 3).
• Với truy vấn 4: Không có đường đi từ thành phố 1 đến 4.
• Với truy vấn 5: Đường đi ngắn nhất từ 3 đến 2 có độ dài 3.