ModricWang的水系法术

题目描述

ModricWang和ZKx是好朋友。ZKx是一位强大的魔法师，掌握各种魔法。今天，ModricWang向ZKx学习水系魔法。

ZKx的魔法面板上有N个点，标号为1~N。ModricWang可以通过魔法让点a和点b之间能通过流量为c的水流。当ModricWang完成M次施法后，ZKx会从点1注入无穷多的水流，并引导它们向点N流动。请你帮ModricWang算出，点N处最多会收到流量为多少的水流？

输入

第一行两个整数，N和M，N为点数，M为边数，点的标号为1~N。

接下来M行，每行三个整数a, b, c, 表示边的两个端点和可以通过的流量的最大值。水流的方向没有限制。保证没有重边自环。

$1 \leq N \leq 1000$

$1 \leq M \leq 100000$

$1 \leq a,b\leq N , a\neq b$

$1 \leq c \leq 10$

输出

输出一个整数，点N处会收到的流量的最大值

输入样例

4 6
1 2 5
1 3 2
1 4 3
2 3 3
2 4 3
3 4 10

输出样例

10

HINT

方向没有限制意思是水可以流回来，也就是水往两个方向都可以流

只能帮你们到这里了