Mạng lưới giao thông của thành phố biểu diễn bằng đồ thị ~N~ đỉnh (Đại diện cho ~N~ thành phố) và ~M~ cạnh (đại diện cho ~M~ cây cầu). Mỗi cây cầu có giới hạn độ cao tối đa của xe chạy qua nó. Hay nói cách khác mỗi cạnh trong đồ thị ứng với một trọng số nguyên dương là chiều cao của cây cầu tương ứng. Tìm đường đi từ ~s~ đến ~t~ (cho trước) sao cho chiều cao của xe có thể đi qua là lớn nhất.

Ví dụ:

Input:

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

Output

2