严格次短行走长度

难度：T4

【知识点：次短路状态】

前置知识：次短路状态及其冻结前置单元。

题目描述与输入

第一行$n$ $m$，随后$m$行无向边$u$ $v$ $w$。起点$1$，终点$n$。求严格次短行走长度。起终点相同时空行走长度为$0$，仍可考虑非空闭合行走。

输出

不存在严格次短行走输出-$1$，否则输出所求整数。

数据范围

$1 \le n \le 80$，$0 \le m \le 500$，$1 \le w \le 9$。无向图，允许重边自环。

样例输入

3 3
1 2 8
1 3 2
3 2 3

样例输出

6

样例说明

终点是$3$，最短$1$→$3$长$2$；来回一次$1$—$3$后再到$3$长$6$，因此严格次短为$6$。