Trong phòng thi Tin học trẻ, Huy gặp một bài toán rất khó nhưng không muốn trở thành gánh nặng của đồng đội nên cần sự trợ giúp của bạn.

Cho đồ thị có hướng gồm ~N~ đỉnh, ~M~ cạnh có trọng số và ~K~ yêu cầu, mỗi yêu cầu có dạng ~(u,v)~. Mảng ~c~ gồm ~K~ phần tử nhận giá trị ~c_i = cost(u_i,v_i)~ (~1 \leq i \leq K)~ với ~cost(u_i, v_i)~ được định nghĩa là trọng số lớn nhất của cạnh trên một đường đi bất kỳ từ ~u~ tới ~v~. Lưu ý với một cặp ~(u, v)~ cố định, ~cost(u, v)~ có thể nhận nhiều giá trị khác nhau tùy thuộc vào đường đi được chọn.

Yêu cầu

~K~ yêu cầu, yêu cầu thứ ~i~ có dạng ~(u_i, v_i)~: hãy chọn ra đường đi tối ưu từ ~u_i \rightarrow v_i~ (~\forall i: 1 \leq i \leq K~) sao cho giá trị tối đa của mảng ~c~ đạt nhỏ nhất. Nói cách khác, hãy tối thiểu hóa giá trị ~\max(cost(u_i, v_i))~ (~\forall i: 1 \leq i \leq K~).

Dữ liệu

• Dòng đầu gồm ba số nguyên dương ~N~, ~M~, ~K~ ~(2 \leq N \leq 2 \times 10 ^ 4;\ M,\ K \leq 10 ^ 5)~.
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo mỗi dòng chứa ba số nguyên dương ~a_i,b_i,w_i~: có cạnh một chiều giữa hai đỉnh ~a_i,\ b_i~ và trọng số là ~w_i~ ~(1 \leq a_i, b_i \leq n,1 \leq w_i \leq 10^9)~.
• Dòng thứ ~i~ trong ~K~ dòng tiếp theo mỗi dòng có hai giá trị ~u_i,v_i\ (u_i \neq v_i)~ yêu cầu bạn gán ~c_i~ = ~cost(u_i,v_i)~ (~1 \leq u, v \leq n~). Nếu tồn tại ~i~ sao cho không có đường đi từ ~u_i~ đến ~v_i~, đáp án của toàn bộ bài toán sẽ là ~-1~.

Kết quả

• Một dòng duy nhất gồm giá trị nhỏ nhất có thể của ~max(c_i)~ (~\forall i: 1 \leq i \leq K)~.

Ví dụ

Input

4 5 3 
1 2 4 
2 3 2 
3 1 3 
4 3 5  
4 1 8 
3 2  
4 2 
2 1 

Output

5

Giải thích

• Với yêu cầu thứ nhất ~c_1~ = ~4~ ~(3 \rightarrow 1 \rightarrow\ 2)~.
• Với yêu cầu thứ hai ~c_2~ = ~5~ ~(4 \rightarrow 3 \rightarrow 1 \rightarrow 2)~.
• Với yêu cầu thứ ba ~c_3~ = ~3~ ~(2 \rightarrow 3 \rightarrow 1)~.