Đàn bò của nông dân John đang luyện tập cho 1 cuộc chạy vượt rào sắp diễn ra. Nông trại của John có N cánh đồng và M con đường (0 < N <= 300, 0 < M <= 25000), mỗi con đường được kí hiệu bởi 2 chỉ số P và Q mô tả 1 đường đi 1 chiều từ P đến Q (0 < P,Q <= N). Ngoài ra, trên mỗi con đường, nông dân John đặt 1 chướng ngại vật độ cao H (0 < H <= 10^6).

Lũ bò sẽ tập chạy trong T vòng (0 < T <= 40000), mỗi vòng chúng sẽ chạy từ đồng cỏ Ai đến Bi (0 < Ai, Bi <= N, Ai ≠ Bi). Do chúng rất lười biếng, nên chúng sẽ chọn con đường mà độ cao của chướng ngại vật cao nhất cần phải vượt qua là thấp nhất. Nói cách khác, nếu gọi x là kết quả của lượt chạy này, không có chướng ngại vật nào trên đường chạy này có độ cao lớn hơn x.

Yêu cầu: Hãy giúp lũ bò chọn ra đường chạy tối ưu.

Input:

• Dòng đầu tiên chứa 3 số nguyên N, M và T

• M dòng tiếp theo, mỗi dòng chứa 3 số nguyên P, Q, H tương ứng

• T dòng tiếp theo, mỗi dòng chứa 2 số nguyên Ai và Bi

Output:

• Đưa ra T dòng, là độ cao của đường chạy tối ưu trong vòng chạy tương ứng, hoặc -1 trong trường hợp không có đường đi từ Ai đến Bi

Sample Input:

5 6 3 
1 2 12 
3 2 8 
1 3 5 
2 5 3 
3 4 4 
2 4 8 
3 4 
1 2 
5 1

Sample output:

4
8
-1