题目描述

求最短路已经难不倒你了。

那么求次短路呢？

N 个点，编号为 1 ~ N。M 条无向边。可能有自环，可能有重边。1 号点与 N 号点是连通的。求 1 号点到 N 号点的次短路。

注：次短路的长度肯定大于最短路的长度。本题中允许多次走同一条边。中途可以多次经过同一个点，包括终点也可以多次经过。

输入格式

第一行：两个整数 N, M

接下来 M 行：每行三个整数 u, v, w 表示 u 和 v 之间有一条长度为 w 的无向边

输出格式

一个整数，表示次短路的长度。

样例输入

4 5
1 2 10
2 4 5
2 3 10
3 4 10
4 4 1

样例输出

16

数据范围

$1 ≤ N ≤ 5000 , 1 ≤ M ≤ 10^5 , 1 ≤ u, v ≤ N, 1 ≤ w ≤ 5000$