Description

约翰修建了一套排水沟，池塘中的水被 排到附近的小溪里。约翰在每条水沟的开头都安装了调节器，可以控制 水流入沟渠的流量。约翰不仅知道每条水沟每分钟可以输送多少加仑的 水，还知道水沟的确切布局。水沟从池塘中流出，相互汇入，形成一个 潜在的复杂网络。需要确定水从池塘输送到溪流的最大流量。

Format

Input

输入包括几个测试用例。每个测试用例的第$1$行都包含两个 整数$N （0≤N ≤200）$和$M （2≤M ≤200）$。$N$ 表示排水沟的数量，$M$ 表示水沟的交叉点数量。交叉点1是池塘。交叉点M 是河流。以下$N$ 行，每行都包含三个整数：$S_i$ 、$E_i$ 和$C_i$ 。$S_i$和$E_i$$（1≤S_i , E_i ≤M）$表示水沟的交叉点。水会从$S_i$流到$E_i$ ，最大流量为$C_i$$（0≤Ci≤10000000）$。

Output

对每个测试用例，都单行输出从池塘中排出水的最大流 量。

Samples

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

50