描述

每当约翰农夫的田地降雨时，贝西最喜爱的苜蓿田上就会形成一个水塘。这意味着苜蓿会被水淹没一段时间，并且需要很长时间才能重新长出来。因此，约翰农夫修建了一系列排水沟渠，这样贝西的苜蓿田就再也不会被水淹没了。相反，水会被排到附近的一条小溪中。作为一名一流的工程师，约翰农夫还在每条沟渠的起点安装了调节器，这样他就可以控制水流进该沟渠的速度。

约翰农夫不仅知道每条沟渠每分钟能输送多少加仑的水，还清楚这些沟渠的确切布局。这些沟渠从水塘引出，相互交错，并以一种可能较为复杂的网络形式流入小溪。

根据所有这些信息，确定水能够从水塘排出并流入小溪的最大速率。对于任何一条给定的沟渠，水只朝一个方向流动，但有可能存在让水形成循环流动的路径。

输入

输入包含多个测试用例。对于每个测试用例： 第一行包含两个用空格分隔的整数 $N$（$0 < N < 200$）和 $M$（$2 < M < 200$） 。其中，$N$ 是约翰农夫挖掘的沟渠数量，$M$ 是这些沟渠的交汇点数量。交汇点 $1$ 是水塘，交汇点 $M$ 是小溪。接下来的 $N$ 行中，每行都包含三个整数 $S_i$ 、$E_i$ 和 $C_i$ 。

输出

对于每个测试用例，输出一个整数，表示水能够从水塘排出的最大速率。

输入数据1

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

输出数据1

50

来源

美国计算机奥林匹克竞赛（USACO）1993年题