题目描述

为了防止池塘里的三叶草被雨水淹没，农夫约翰挖了很多排水沟，将雨水排到河中。

约翰在每一个沟渠中都安装了调节器，借此可以调整水流入该沟渠的速度。

约翰不仅知道每个沟渠的具体排水速度，还知道它们的分布位置。

对于任何给定的沟渠，水都只能沿着一个方向流动，但是水有可能循环流动。

根据给定的信息，请你求出池塘排水到河中的最大速率。

输入格式

第一行包含两个整数 $N$ 和 $M$，$N$ 表示排水沟的数量，$M$ 是沟渠的交叉点数。

交叉点 $1$ 处是池塘，交叉点 $M$ 处是河。

接下来 $N$ 行，每行包含三个整数 $S_i, E_i, C_i$，$S_i$ 和 $E_i$ 是一条沟渠的两个交叉点，水流从 $S_i$ 流向 $E_i$，$C_i$ 是水流最大速率。

输出格式

输出一个整数，表示水从池塘排到河中的最大速率。

样例

输入样例：

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

输出样例：

50

样例解释

排水沟网络：

• 从1到2，容量40
• 从1到4，容量20
• 从2到4，容量20
• 从2到3，容量30
• 从3到4，容量10

池塘是节点1，河是节点4。

最大流计算可得最大排水速率为50（例如，1→2:30, 1→4:20, 2→3:10, 2→4:20, 3→4:10）。

数据范围

• $0 \le N \le 200$
• $2 \le M \le 200$
• $1 \le S_i, E_i \le M$
• $0 \le C_i \le 10^7$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB