Migrated from Lutece 1143 传输数据

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

机房里面有$m$台电脑，$n$台网线，每条网线都每秒中最多传送的数据量，现在需要你计算从标号为1的电脑传送数据到编号为$m$的电脑，问一秒内最多传送多少数据?

Input

第1行: 两个用空格分开的整数$N (0 \leq N \leq 200)$和 $M (2 \leq M \leq 200)$。$N$网线的数量，$M$是电脑的数量。

第二行到第$N+1$行: 每行有三个整数，$Si$，$Ei$ 和 $Ci$。$Si$ 和 $Ei$ $(1 \leq Si, Ei \leq M)$ 指明电脑编号，数据从 $Si$ 流向 $Ei$。$Ci (0 \leq Ci \leq 10,000,000)$是这条网线的最大容量。

Output

输出一个整数，即排水的最大流量。

Samples

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

50

Resources

2015 UESTC Training for Graph Theory