Description

小明经常看到机场、地铁站会有平地上的“电梯”方便运大行李的旅客节省体力。他想，如果给学校的连廊也装一个，岂不是很有意思。

已知连廊的起点、终点，以及每个路口和路口之间道路的行走时间。安装加速通道的道路，行走时间减半（除法向下取整） 。

假设 只能给一条道路安装加速通道 ，装在哪条道路，能让起点到终点的时间最短呢？帮小明计算一下安装加速通道后通过连廊的最短时间。

Input

不超过50组测试数据，每组测试数据第一行两个整数：n，m 分别表示路口数和道路数。

接下来 m 行，每行三个数 s，e, t （1 <= s < e <= n，1 <= t <= 10^6）表示 s 与 e 之间有一条双向道路，该道路安装加速通道前所需行走时间为t。

其中起点编号为 1，终点编号为 n。

2 <= n <= 100，1 <= m <= 2000。

数据保证起点与终点连通。

Output

每组数据输出一行，一个整数，表示加装加速通道后起点到终点的最短时间。

3 3
1 2 6
2 3 6
1 3 13
5 6
4 3 3
4 5 18
3 4 0
3 5 2
2 3 10
4 1 6

6
5