問題文

N 個のタンクと M 本のパイプがあります、j 本目のパイプはタンク A_j からタンク B_j の方向に毎秒 C_j リットルまで水を流すことができます。
タンク 1 からタンク N まで毎秒最大何リットルの水を流すことができますか。ただし、タンクに水を貯めることはできないと考えてかまいません。

制約

• 2 \leq N \leq 400
• 1 \leq M \leq 400
• 1 \leq A_j , B_j \leq N
• A_j \neq B_j
• j\neq k ならば (A_j,B_j) \neq (A_k,B_k)
• 0 \leq C_j \leq 5000
• 答えは 5000 以下の整数
• 入力はすべて整数

入力例 1

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

出力例 1

8