时间限制：1秒　　内存限制：256M

---

【题目描述】

　　农夫约翰必须送一个包裹给农民丹，正准备开始他的旅程。为了维持和平，他给路上遇到的每头牛一个好吃的东西，当然，FJ为了节俭想尽可能少遇到牛。

　　FJ 绘制了一张有 \(N\) 个谷仓的地图，由 \(M\) 条双向路径连接，每条路上有 \(C_i\) 头奶牛。一条路连接两个不同的谷仓：\(A_i\) 和 \(B_i（ A_i≠B_i）\)。两个谷仓间可能有一条以上的路径直接连接。FJ目前在谷仓 1，农民丹在谷仓 \(N\)。

　　考虑下面的地图：

　　农民约翰的最佳路径是从 1-> 2 -> 4 -> 5 -> 6，因为这会花费他 1 + 0 + 3 + 1 = 5 个食物。

　　告诉你FJ的地图，他最少应该带多少食物？他并不关心他的旅程的长度。

【输入格式】

　　第 1 行：两个用空格隔开的整数：\(N\) 和 \(M\)。
　　第 2..\(M+1\)：三个用空格隔开的整数：\(A_i，B_i，C_i\)。

【输出格式】

　　第 1 行：最低数量的对待，FJ必须携带。

【输入输出样例】

　Input

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

　Output

5

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤50000\)，\(1≤M≤50000\)，\(0≤C_i≤1,000\)

【来源】

　　Mr.he