题目描述

Ich weiss nicht, was soll es bedeuten,
Dass ich so traurig bin;
Ein Maerchen aus alten Zeiten,
Das kommt mir nicht aus dem Sinn.

士郎中了可爱的魔法少女伊莉雅苏菲尔 · 冯 · 爱因兹贝伦的魔眼之后，被带回了伊莉雅的城堡。伊莉雅旋即「离开」去捉 Rin 和Saber，但机智的士郎知道 Rin 和 Saber 已经来到城堡救他，而走的伊莉雅只不过是替身。

然而，为了攒足 Saber 的好感度防止某日在麻婆神父面前被杀死，士郎决定「逃出」爱因兹贝伦城堡。由于 Archer 正在向城堡赶来，士郎决定尽可能拖延时间以防独自面对 Berserker 的袭击。

不过，Servant 的感知和思考都是敏锐的，因此士郎如果绕了太远路，会被 Saber 发现而反而减少好感度，所以士郎决定走在比最短路长的所有路径中最短的一条路径。

当然，Rin 的感知也是很敏锐的，所以士郎如果走到了已经走到过的某个点，那么就立刻会被 Rin 发现而以归还十年份魔力的宝石作为对 Saber 的保密条件哦。本来故事这样就结束了，可是还有默默围观的伊莉雅。伊莉雅比 Saber 和 Rin 想得多些（雾），如果一条边 $(u, v, w)$ 可能出现在最短路径上，顺序是 $u \rightarrow v$（所有边权为正），那么士郎如果沿 $v \rightarrow u$ 走了这条边，会立刻被伊莉雅发现而被做成人偶哦。

不妨设伊莉雅的房间（士郎所在位置）为 $1$ 号点，城堡大厅为 $n$ 号点。很显然，伊莉雅没有远坂间桐樱一样在居所设置机关（参见某 BE 的道场）的兴趣，因此每条边都是双向边。

输入格式

第一行两个正整数 $n, m$，分别表示点数和边数。

接下来 $m$ 行每行三个正整数 $u, v, w$，表示点 $u$ 与点 $v$ 之间有一条权值为 $w$ 的边。

输出格式

第一行一个整数，表示所求路径的长度，若不存在则输出 -1。

样例输入

2 2
1 2 1
1 2 2

样例输出

2

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10 ^ 5$，$1 \le m \le 5 \times 10 ^ 5$，$1 \le w \le 10 ^ 3$。