An đang tham quan Khu du lịch Hồ Núi Cốc. Khu vực được mô hình hóa bởi một đồ thị có hướng không chu trình gồm ~N~ địa điểm và ~M~ lối đi một chiều. Các địa điểm được đánh số từ ~1~ đến ~N~; lối đi thứ ~i~ nối từ ~u_i~ đến ~v_i~ và có mức nguy hiểm ~d_i~.

An bắt đầu tại địa điểm ~1~ và muốn đi qua đúng ~K~ lối đi. Mức nguy hiểm của một hành trình là giá trị lớn nhất trong các mức nguy hiểm của những lối đi thuộc hành trình đó.

Hãy tìm mức nguy hiểm nhỏ nhất có thể của một hành trình hợp lệ. Nếu không tồn tại hành trình đi qua đúng ~K~ lối đi, hãy in ra ~-1~.

Input

• Dòng đầu chứa ba số nguyên ~N, M, K~ ~(1 \le N, K \le 200000, 1 \le M \le 500000)~.

• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, d_i~ ~(1 \le u_i, v_i \le N, 1 \le d_i \le 10^9)~, mô tả một lối đi một chiều. Dữ liệu bảo đảm đồ thị không có chu trình.

Output

• In ra mức nguy hiểm nhỏ nhất của một hành trình bắt đầu tại địa điểm ~1~ và đi qua đúng ~K~ lối đi, hoặc ~-1~ nếu không có hành trình như vậy.

Scoring

Sample Input 1

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

Sample Output 1

5

Sample Input 2

6 6 4
1 2 3
1 3 6
2 4 2
3 4 1
4 5 4
2 6 5

Sample Output 2

-1

Notes

Trong ví dụ thứ nhất, hành trình ~1 \rightarrow 3 \rightarrow 5 \rightarrow 7~ đi qua đúng ba lối đi và có mức nguy hiểm ~\max(4, 5, 5) = 5~. Không có hành trình hợp lệ nào chỉ sử dụng các lối đi có mức nguy hiểm nhỏ hơn ~5~.