题目描述

这里有N（2<=N<=2000）个农场，标号为1到N。贝西开始在1号农场。。农场之间总共有 M（1≤M≤10^4 ）条双向道路，所有道路的总长度不超过10^9。某些农场之间会有双向通道连接。
贝西准备了一个水箱，用来存放路途中所需要的水。到一个农场可以补充满水箱里的水，但是在途中，每经过1单位的距离就会消耗掉1单位的水。
请你帮助贝西设计一个程序，计算出最少需要多大的水箱才能够从农场1到达所有的农场。

输入格式

第一行两个整数N, M 第二行到第M+1行：每行三个数X,Y,Z， 表示X农场到Y农场之间有一条长度为Z的路。

输出格式

输出这个水箱最少需要多大。

样例

input

3 3
1 2 23
2 3 1000
1 3 43

output

43