题目描述
不知道这个教育局搞什么鬼名堂,竟然要把全县的学生分散开,这就惨了,运输问题就很严重。W校长只好从外面调集车辆(为了省钞票,CG学校把车停在了N个点上,包括学校和目的地,但可能有些点之间没有连线,甚至有可能无法从学校开到目的地)。同样,Z主任念鄙人2次为校争得至高无上的荣誉(PS,就是鄙人和唐XX,鄙人拿2个,唐XX拿1个。只可惜,我在小学里接触到OI的时候,姓唐的已经去绍一中了),就命令拿出一种方案,每次运出的学生数最多。
输入格式
第1行,二个数,M,N。
接下来M行,每行3个数,A,B,S(0<A,B<=N,0〈S〈=1000〉表示从A点到B点可以运S人(但从B到A不能运人)。
其中,A,B会有2个特殊值:1 —— 本校 , N —— 目的地
数据范围:0 <N <=100,N-1<=M <=200。其他输入的数不超过1000。
输出格式
一个数,表示一次最多能运的学生数。
样例输入
样例输出