春日影

题号：NC305764
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 你想逃避吗？长崎素世拉着丰川祥子，素世（长崎素世 / Soyo）情绪激烈地质问丰川祥子（祥子 Saki），逼她直面睦（Mutsumi）的现状与自己过去在 CRYCHIC 及 Ave Mujica 中的责任，而不要继续以冷漠和回避逃避问题。素世的话语既愤怒又绝望，强行撕开了祥子长期掩藏的防线，使祥子开始动摇并露出脆弱的一面。
$\hspace{15pt}$ 同为翔子的加藤翔子决定帮助丰川祥子逃离素世的逮捕，具体来说丰川祥子在所在的城市里面进行逃避，只需要到达羽丘女子学园里面，作为不同学校的长崎素世就没法进入该校。

$\hspace{15pt}$ 假设当前两人起点在编号为 $1$ 的地点，而祥子的学校羽丘女子学园在编号为 $n$ 的地点，整个城市可简化为一张带权无向图，祥子需要从顶点 $1$ 出发，目标是到达顶点 $n$ ，每条路的长度为非负整数，走一条路需要付出其路的长度大小的时间。
$\hspace{15pt}$ 加藤翔子能够做的事情是：如果祥子沿无向边 $u\!-\!v$ 从 $u$ 走到 $v$ ，紧接着立刻沿同一条边从 $v$ 返回到 $u$ （即连续走了该边两次： $u\to v$ 然后 $v\to u$ ），则在祥子返回到 $u$ 后的下一次移动（也就是从 $u$ 出发的下一个地点，不论是哪一条边），加藤翔子将会提供一辆梅赛德斯-迈巴赫 S 650 Pullman (VV222) 光速带着祥子到达下一个地点（花费时间为 $0$ ）。该“迈巴赫”在达成条件后不可以被保留，从 $u$ 点离开后立即失效。

$\hspace{15pt}$ 现在，给定一张地图，代表城市和城市里面的路径，请你计算祥子至少需要花费多长时间才能到达羽丘女子学园（即从顶点 $1$ 到顶点 $n$ 的最小花费时间）。特别地，如果 $n$ 无法到达，直接输出 $-1$ 。

输入描述:

第一行输入两个整数 ，表示图的顶点数、边数。
此后  行，第  行输入三个整数 ，表示第  条无向边连接顶点  和 ，边权为 。图允许多重边和自环，不保证图是联通的。

输出描述:

如果顶点  无法到达，直接输出 ；否则，输出一个整数，表示在加藤翔子的帮助下，丰川翔子从  到  的最小可能代价。

示例1

输入

复制

输出

复制

说明

在这个样例中，其中一条最优路线为：
第一步，（费用 ）；
第二步，（费用 ，触发“来回”，获得一次“迈巴赫”）；
第三步，（费用 ，使用“迈巴赫”）；
第四步，（费用 ）。
综上，最小总费用为 。

示例2

输入

复制

输出

复制

说明

在这个样例中，其中一条最优路线为：
第一步，（费用 ）；
第二步，（费用 ，触发“来回”，获得一次“迈巴赫”）；
第三步，（费用 ，不使用“迈巴赫”；与此同时，再次触发“来回”，获得一次“迈巴赫”）；
第四步，（费用 ，使用“迈巴赫”）；
第五步，（费用 ）。
综上，最小总费用为 。

示例3

输入

复制

3 2
1 2 114514
1 1 1919810

输出

复制

-1

示例4

输入

复制

输出

复制