P11898 移动迷宫

花生在电线杆的小广告上看到大侦探福尔魔斯正在招募助手帮助他抓住穷凶极恶的杀人魔：不知道。 花生出于某种原因来到了福尔魔斯的住处接受面试。但福尔魔斯住在一个...移动迷宫里？

这个迷宫一共有 $n$ 个房间和 $m$ 条双向道路。第 $i$ 条道路连接 $u_i$ 和 $v_i$ 这两个房间，长度为 $w_i$。 福尔魔斯的迷宫是是会变化的：每通过一条道路（到达一个房间），所有道路都会伸缩，如果原本长度是 $t$，伸缩后长度会变化为 $\dfrac{1}{1-t}\bmod 754974721$。（如果你不知道分数如何取模，可移步 [P2613](https://www.luogu.com.cn/problem/P2613)；同时注意有可能涉及负数取模） 花生位于 $1$ 号房间。根据花生的测算，福尔魔斯就住在 $n$ 号房间。 请你帮帮花生最快到达 $n$ 号房间找到福尔魔斯。 ------ 负数取模：$x0$，$x$ 对 $p$ 取模的结果等于 $x+p$ 对 $p$ 取模的结果。 $754974721$ 是一个质数。

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

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

### 样例 #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