题目描述

Bessie搬到了一个新的农场，有时候他会回去看他的老朋友。

但是他不想很快的回去，他喜欢欣赏沿途的风景，所以他会选择次短路，因为她知道一定有一条次短路。

这个乡村有$\red{R}$($\red{1<=R<=100000}$)条双向道路，每一条连接$\red{N}$($\red{1<=N<=5000}$)个点中的两个。

Bessie在1号节点，他的朋友家是$\red n$号节点.

输入格式

第一行：两个整数$\red N$和$\red R$ 接下来R行:每行包含三个整数，$\red A$，$\red B$,$\red D$，表示一条连接$\red A$与$\red B$的长度为$\red D$的路径

输出格式

输出$\red 1$到$\red n$的次短路

样例

输入样例

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出格式

450

提示

两条路线：1 - > 2 - > 4（长度100 + 200 = 300）和1 - > 2 - > 3 - > 4（长度100 + 250 + 100 = 450）