소스에서 목적지까지 자료를 일정한 크기로 잘라서 보내는 방법이 있고 , 소스에서 목적지까지 연결을 유지한 후에 자료를 한 꺼번에 보내는 방법이 있다.

후자의 방법으로 자료를 전달하는 경우 한 번에 전달할 수 있는 최대 데이터의 크기와 패스를 찾는 것이 문제이다.

예를 들어 , 아래 그림에서 간선위 숫자가 한 번에 보낼수 있는 데이터의 한계치라고 할 때 ,

1 - 2 - 3 - 5 로 연결 후 자료를 전달하는 경우 크기 3 의 데이터를 보낼수 있다.

최대로 많은 데이터를 보내기 위해서는 1 - 2 - 5 로 연결하는 경우 한 번에 크기 5 의 데이터를 보낼수 있다. 이 크기가 최대이다.

입력

• 첫 줄에는 정점의 수 n ( 2 <= n <= 100) 이 입력으로 주어지고,
• 다을 줄에는 출발, 도착 정점이 다음 줄에는 간선과 해당 간선의 한계치가 주어진다. 입력의 끝은 EOF 이다.

입력 데이터는 사이클이 발생하지 않는다.

출력

입출력 예

입력

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

출력

5
1 2 5

.........[ hint ]