비가 올때 마다 연못이 넘져 순돌이의 클로버 밭으로 물이 넘져 막대한 손해을 본다. 그래서 순돌이는 물이 넘치지 못하도록 여러개의 도랑을 만들었다.

순돌이는 아버지의 도움을 받아(참고로 순돌이 아버지는 일급 공학자) 각 도랑의 시작 부분에 조절기를 설치 했다. 그래서 도랑으로 들어가는 물의 양을 조절할 수가 있다.

순돌이는 또한 이 도랑으로 보낼수 있는 물의 양을 알고 있다.이 양보다 넘치면 이 도랑의 한계량을 벗어나서 물이 넘친다. 이 모든 정보를 받아 연못에서 보낼수 있는 최대 물의 양을 구하는 게 문제이다. 단 , 도랑은 한 방향으로만 물이 흐르지만 여러도랑의 거쳐 사이클이 만들어질수는 있다.

입력

라인의 첫 줄은 N (0 <= N <= 200) and M (2 <= M <= 200)이 주어진다. N 은 도랑의 수이고 M 은 도랑의 교차지점의 수이고 1 번은 연못이고 , M 번은 출구이다.

다음 N 라인은 세 정수 S E C 가 주어진다. S 는 도랑의 시작번호이고 E 는 도착지점이고 C 는 도랑의 한계 량이다. (1 <= S, E <= M 이고 0 <= C <= 10,000,000)

출력

입출력 예

입력

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

출력

50

보충 설명

출처:usaco