严格次短比最短多多少

难度：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

样例输出

4

样例说明

终点$3$的最短为$2$、严格次短$6$，差为$4$。