Có n thành phố và m con đường. Nhiệm vụ của bạn là xử lý q truy vấn: xác định độ dài của tuyến đường ngắn nhất giữa hai thành phố x và y.

Input

Dòng đầu tiên chứa 3 số nguyên n, m và q: số thành phố, số đường và truy vấn.

Khi đó có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: có một con đường nối giữa thành phố u và v có chiều dài là w. Mọi con đường đều là đường hai chiều.

Cuối cùng là q dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên x và y: xác định độ dài của tuyến đường ngắn nhất giữa thành phố x và y.

Output In độ dài của tuyến đường ngắn nhất cho mỗi truy vấn. Nếu không có lộ trình, thay vào đó hãy in -1.

Hạn chế

~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~

Examples

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

​