Trong một mạng giao thông liên thông gồm ~ n ~ nút và ~ m ~ đoạn đường giữa một số cặp nút, mỗi đoạn đường đều có giới hạn tải trọng xe. Một xe cần đi từ nút 1 đến nút ~ n ~. Cần chọn cho xe một hành trình sao cho theo hành trình đó, xe có trọng tải được phép lớn nhất.

Dữ liệu vào

• Dòng đầu tiên ghi hai số ~ n,m ~.
• Trong ~ m ~ dòng tiếp theo, mỗi dòng ghi ba số nguyên dương, hai số đầu là tên hai nút có đoạn đường nối trực tiếp, số thứ ba là tải trọng cho phép.

Kết quả

Ghi một số nguyên là tải trọng lớn nhất tìm được

Ràng buộc

• ~ 2 ≤ n ≤ 100 000 ~
• ~ 1 ≤ m ≤ 200 000 ~
• ~ 1 ≤ w ≤ 10^9 ~

Ví dụ:

Input 1

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

Output 1

4