어떤 지역은 p개의 지점과 w개의 양방향 통로로 이루어져 있다. 각 통로에는 폭이 정해져 있으며, 한 번에 지나갈 수 있는 규모는 그 폭에 의해 제한된다.

출발 지점 c에서 도착 지점 v까지 하나의 경로를 정하려고 한다. 경로의 성능은 그 경로에 포함된 통로들 중 가장 폭이 좁은 통로의 폭으로 정한다.

여러 가능한 경로 중에서, 이 값이 최대가 되는 경로를 선택했다고 하자.

지역의 연결 정보가 주어졌을 때, 선택된 경로에서 가장 좁은 통로의 폭이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫 줄에 p와 w가 공백을 사이에 두고 주어진다. 2 ≤ p ≤ 1,000, 1 ≤ w ≤ 50,000이다.

다음 줄에 출발 지점 c와 도착 지점 v가 공백을 사이에 두고 주어진다. 0 ≤ c, v < p, c ≠ v이다.

다음 w줄에 통로가 연결하는 두 지점 wstart, wend와 통로의 폭 wwidth가 공백을 사이에 두고 주어진다.

0 ≤ wstart, wend < p, wstart ≠ wend, 1 ≤ wwidth ≤ 1,000이다.

출력

조건을 만족하는 경로에서, 그 경로에 있는 통로 중 가장 좁은 통로의 폭을 출력한다.

예제 입력 1

7 11
3 5
0 1 15
0 2 23
1 2 16
1 3 27
2 4 3
2 6 21
3 4 14
3 5 10
4 5 50
4 6 9
5 6 42

예제 출력 1

16