说明

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

输入格式

第一行：两个用空格分开的整数 $N$（$0 \le N \le 200$）和 $M$（$2 \le M \le 200$）。$N$ 是农夫 John 已经挖好的排水沟的数量，$M$ 是排水沟交叉点的数量。交点 $1$ 是水潭，交点 $M$ 是小溪。

第二行到第 $N + 1$ 行：每行有三个整数，$S_i, E_i, C_i$。$S_i$ 和 $E_i$（$1 \le S_i, E_i \le M$）指明排水沟两端的交点，雨水从 $S_i$ 流向 $E_i$。$C_i$（$0 \le C_i \le {10}^7$）是这条排水沟的最大容量。

输出格式

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

样例

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

50

提示

题目翻译来自NOCOW。

USACO Training Section 4.2

【数据范围】

对于 $100 \%$ 的数据，$0 \le N, M \le 200$，$0 \le C_i \le {10}^7$。