Candy-collecting robot

Time limit1sMemory limit512 MB

Summary

Given a house graph with an integer capacity on every corridor, find the maximum number of unit-capacity routes from room 1 to room n.

Level: Medium7 of 10
Topics: Graph, BFS, Implementation, Math
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Examples2

Example 1
Input
```
3 2
1 2 6
2 3 5
```
Expected output
```
5
```
Example 2
Input
```
4 4
1 2 7
1 3 2
2 3 4
3 4 10
```
Expected output
```
6
```