题目背景

花生在电线杆的小广告上看到大侦探福尔魔斯正在招募助手帮助他抓住穷凶极恶的杀人魔：不知道。

花生出于某种原因来到了福尔魔斯的住处接受面试。但福尔魔斯住在一个...移动迷宫里？

题目描述

这个迷宫一共有 $n$ 个房间和 $m$ 条双向道路。第 $i$ 条道路连接 $u_i$ 和 $v_i$ 这两个房间，长度为 $w_i$。

福尔魔斯的迷宫是是会变化的：每通过一条道路（到达一个房间），所有道路都会伸缩，如果原本长度是 $t$，伸缩后长度会变化为 $\dfrac{1}{1-t}\bmod 754974721$。（如果你不知道分数如何取模，可移步 P2613；同时注意有可能涉及负数取模）

花生位于 $1$ 号房间。根据花生的测算，福尔魔斯就住在 $n$ 号房间。

请你帮帮花生最快到达 $n$ 号房间找到福尔魔斯。

负数取模：$x<0,p>0$，$x$ 对 $p$ 取模的结果等于 $x+p$ 对 $p$ 取模的结果。

$754974721$ 是一个质数。

输入格式

第一行，两个正整数 $n,m$。

之后 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示一条边。

输出格式

输出一个正整数，表示到达 $n$ 号房间的最短距离。

5 7
1 2 3
2 3 8
3 5 1000
2 4 100
4 5 6
1 4 78888
1 3 114514

151073832

6 8
1 3 100000000
1 5 200000000
2 5 300000000
2 6 400000000
3 4 500000000
5 6 600000000
4 5 700000000
3 6 303063652

403063652

提示

样例 #1 解释：

沿路径 $1\rightarrow 4\rightarrow5$，路径长度为 $78888+150994944 = 151073832$。

对于 $30\%$ 的数据，$n\le 10$。

对于另外 $30\%$ 的数据，所有边边权相等。

对于 $100\%$ 的数据，$1\le n,m\le 10^5$，保证是一张连通图，$1\le u_i,v_i\le n$，$1<w_i<754974721$，保证无论任何时刻不会出现边权为 $1$ 的边。

所有输入的数都是整数。

后记：
花生到达福尔魔斯住的房间后，看见福尔魔斯正盯着显示屏目不转睛：“你在看什么？”
福尔魔斯：“不知道。”