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

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(q\): số lượng thành phố, con đường và truy vấn.
• Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): có một con đường giữa các thành phố \(a\) và \(b\) mà độ dài của nó là \(c\). Tất cả con đường đều là con đường hai chiều.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(a\) và \(b\): xác định độ dài của tuyến đường ngắn nhất giữa các thành phố \(a\) và \(b\).

Output

• In độ dài của tuyến đường ngắn nhất với mỗi truy vấn. Nếu không có tuyến đường nào, in \(-1\) thay vào đó.

Constraints

• \(1 \le n \le 500\)
• \(1 \le m \le n^2\)
• \(1 \le q \le 10^5\)
• \(1 \le a,b \le n\)
• \(1 \le c \le 10^9\)

Example

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