掘地求生

“大事不妙！”

伴随着这一声惊呼，老K的膝盖中箭了，但是老K是科学家，他怎么可能乖乖的死亡呢，于是他使用了遁地外挂企图苟到吃鸡，这个时候正义的地球人出现了，他发现以他所在的点挖地下去可以找到旧时人埋下的水管，水管的尽头就是老K。且水管存在n个节点，某些节点之间存在一根管道，容量为ci，且正义的地球人所在的点刚好为1，老k所在的点为n，由于主场作战，正义的地球人可以无限的打出元气弹，但是元气弹穿过一个管道容量小于自身的时候它就会消失一部分只留下管道容量的能量，现在假设给出了水管的分布和具体每根的容量，请问老K在1s内最多受到多少伤害。

两个正整数 n,m(1<n,m<=500)

借下来m行给出三个如下形式的数

a,b,c 表示有一条连接a，b的水管容量是c 其中(1<=a,b<=n,0<c<1000);

一行一个整数  表示老K在此种情况下最多每秒收到多少伤害

5 5
1 2 2
1 3 2
2 4 2
3 4 2
4 5 1
3 1
1 2 1

1
0

假设从1不可到达n则输出0， (正义的地球人，请举起你们的双手