在某市有N个地点（编号1~N），各个地点之间存在着M条双向的道路。每条道路有一个承重上限V。明明想要从S点运送一些货物到T点。但是，由于货物可能会超重，对于承重上限为V的道路来说，只有当货物重量E<=V时，才能通过（与货物相比，明明和其余物品重量可以忽略）。明明想知道，若成功从S点到T点，他最多可以运送多重的货物。设1号点为S点，N号点为T点。保证1号点与N号点连通。
第一行为正整数N，M，表示地点数和道路条数。
第2 行到第M+1 行里，有3个正整数Si,Ti，Vi。表示Si和Ti的道路的承重上限是Vi。
满足要求的最大货物质量。
7 9
1 2 100
2 7 70
1 3 50
3 4 41
2 4 60
2 6 9
4 5 72
5 6 55
6 7 63
70
【数据范围】
对于40%的数据有N≤ 1000, M≤ 2500。
对于100%的数据有N≤ 200000， M≤250000。