Vương quốc Miraland

Vương quốc Miraland có \(n\) thành phố được kết nối với nhau bởi \(m\) con đường. Vì vua Miral rất quan tâm đến hệ thống giao thông, ông muốn biết khoảng cách ngắn nhất giữa hai thành phố bất kỳ để dễ dàng điều phối quân đội và thương mại.

Bạn được giao nhiệm vụ như một nhà chiến lược, hãy giúp nhà vua trả lời \(q\) truy vấn về khoảng cách ngắn nhất giữa hai thành phố trong vương quốc!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(q\) --- số thành phố, số con đường và số truy vấn của nhà vua.

• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\), \(c\) --- có một con đường hai chiều giữa thành phố \(a\) và thành phố \(b\) với độ dài là \(c\).

• Cuối cùng, có \(q\) dòng, mỗi dòng chứa hai số nguyên \(x\), \(y\) --- nhà vua muốn biết khoảng cách ngắn nhất giữa thành phố \(x\) và thành phố \(y\).

Output

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

Example

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

5
5
8
-1
3