Candy-collecting robot

Seokhwan walks around the house and drops candy in the corridors. Seongwon builds a small cleaning robot to clean up the mess.

The house has $n$ rooms numbered $1$ to $n$ and $m$ corridors. Each corridor connects two different rooms and can be walked in either direction. Candy lies only in corridors, and each corridor holds a fixed number of candies. Rooms hold no candy.

A robot follows a start room, a destination room, and a route entered by Seongwon. It moves only through corridors that still hold candy, and it picks up exactly $1$ candy each time it passes through a corridor. Seongwon enters only routes that satisfy this condition.

Seongwon sends every robot from room $1$ to room $n$. Determine the largest number of robots that can be set up without taking more candies from any corridor than it holds.

The first line contains the number of rooms $n$ ($2 \le n \le 300$) and the number of corridors $m$ ($1 \le m \le 5000$), separated by a space.

Each of the next $m$ lines contains corridor information. Each line contains three positive integers $a$, $b$, and $c$, separated by spaces. They mean that the corridor connecting room $a$ and room $b$ holds $c$ candies. ($a \ne b$, $1 \le a, b \le n$, $1 \le c \le 100$)

Print the largest number of robots that can be sent from room $1$ to room $n$.