巴伊托奇亚王国的国王，紧跟全球潮流，决定对所有能征税的东西征税。最近推出的税种是所谓的旅行税，每个在国内旅行的人都必须缴纳。

每条巴伊托奇亚的道路都有一个税率。在巴伊托奇亚旅行时，每当穿越一个城市时，必须在当地政府缴纳税款，这个税额计算方式为：取驶入该城市所经过道路的税率与驶离该城市所经过道路的税率中的最大值。在旅行路线的起点城市和终点城市，也需要缴纳税款——这时，计算税款时只考虑一条道路。

你的朋友巴伊塔扎尔准备从巴伊托夫前往巴伊塔瓦旅行。请帮助他规划一条路线，使他支付的税款总额尽可能少。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100,000$, $1 \le m \le 200,000$），分别表示城市的数量和巴伊托奇亚道路的数量。城市编号从 1 到 $n$。

接下来的 $m$ 行描述道路：在第 $i$ 行有三个整数 $a_{i}$, $b_{i}$, $c_{i}$（$1 \le a_{i}, b_{i} \le n$, $a_{i} \ne b_{i}$, $1 \le c_{i} \le 1,000,000$）。它们表示城市 $a_{i}$ 和 $b_{i}$ 之间有一条双向道路，该道路的税率为 $c_{i}$ 巴伊塔拉。任意一对城市之间至多有一条道路。

输出格式

输出的唯一一行应包含一个整数——从巴伊托夫（编号为 1 的城市）到巴伊塔瓦（编号为 $n$ 的城市）的最小旅行总税费（单位：巴伊塔拉）。你可以假设总是存在一条道路序列将这两个城市连接起来。

示例

输入

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

输出

12

说明

在上面的例子中，最优路线经过城市 1、3、2 和 4。依次需要支付的税额为 2、max(2, 1) = 2、max(1, 4) = 4 和 4，总共为 12 巴伊塔拉。