사탕 줍는 로봇

석환이는 집 안을 돌아다니며 복도에 사탕을 뿌린다. 성원이는 어질러진 집을 청소하려고 작은 청소 로봇을 만들었다.

집에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 방이 있고, 서로 다른 두 방을 잇는 $m$개의 복도가 있다. 복도는 양쪽으로 자유롭게 오갈 수 있다. 사탕은 복도에만 있고 각 복도에는 일정한 개수의 사탕이 있다. 방 안에는 사탕이 없다.

로봇은 성원이가 입력한 시작 방, 도착 방, 이동 경로에 따라 움직인다. 로봇은 사탕이 남은 복도로만 이동할 수 있고, 복도 하나를 지날 때마다 그 복도의 사탕을 딱 $1$개 줍는다. 성원이는 이 조건을 만족하는 경로만 로봇에 입력한다.

성원이는 모든 로봇이 $1$번 방에서 출발해 $n$번 방에 도착하도록 경로를 정한다. 복도의 사탕 개수를 초과하지 않는 범위에서 세팅할 수 있는 로봇 대수의 최댓값을 구한다.

첫째 줄에 방의 개수 $n$($2 \le n \le 300$)과 복도의 개수 $m$($1 \le m \le 5000$)이 공백으로 구분되어 주어진다.

둘째 줄부터 $m$개의 줄에 복도 정보가 하나씩 주어진다. 각 줄에는 세 자연수 $a$, $b$, $c$가 공백으로 구분되어 주어진다. 이는 $a$번 방과 $b$번 방을 잇는 복도에 사탕이 $c$개 있다는 뜻이다. ($a \ne b$, $1 \le a, b \le n$, $1 \le c \le 100$)

첫째 줄에 $1$번 방에서 $n$번 방으로 보낼 수 있는 로봇 대수의 최댓값을 출력한다.