题目描述

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

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

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

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

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

输入格式

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

交叉点$\red {1}$处是池塘，交叉点$\red {M}$处是河。

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

输出格式

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

样例

输入样例

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

输出样例

50

提示

$\red {0≤N≤200}$,

$\red {2≤M≤200}$,

$\red {1≤S _i~ ,E_i~ ≤M}$,

$\red {0≤C _i~ ≤10^7}$