|
Drainage Ditches
草地排水
Hal Burch
译 by Felicia Crazy
在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名�
涣鞯募际Γ┓蛟己惨丫诿刻跖潘档囊欢税采狭丝刂破鳎庋梢钥刂屏魅肱潘档乃髁俊�
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大
流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
PROGRAM
NAME:ditch
INPUT FORMAT
| 第1行: |
两个用空格分开的整数N (0 <= N <= 200)
和 M (2 <= M <=
200)。N是农夫约翰已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。 |
| 第二行到第N+1行: |
每行有三个整数，Si, Ei, 和 Ci。Si
和 Ei (1 <= Si, Ei <= M)
指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0
<= Ci <= 10,000,000)是这条排水沟的最大容量。 |
SAMPLE INPUT (file
ditch.in)
5 4
1 2 40
1 4 20
2 4 20
2 3
30
3 4 10
OUTPUT FORMAT
输出一个整数，即排水的最大流量。
SAMPLE OUTPUT (file
ditch.out)
50 |