P11898 Moving Maze

Huasheng saw a small ad on a utility pole saying that the great detective Sherlock Holmes was recruiting assistants to help him catch a vicious murderer: “I don’t know”. For some reason, Huasheng came to Holmes’s residence for an interview. But Holmes lives in a… moving maze?

This maze has $n$ rooms and $m$ bidirectional roads. The $i$-th road connects rooms $u_i$ and $v_i$, with length $w_i$. Holmes’s maze changes over time: every time you pass through a road (arrive at a room), all roads will expand or shrink. If a road’s original length is $t$, then after the change its length becomes $\dfrac{1}{1-t}\bmod 754974721$. (If you do not know how to take a fraction modulo, see [P2613](https://www.luogu.com.cn/problem/P2613); also note that negative values modulo may be involved.) Huasheng is in room $1$. According to Huasheng’s calculations, Holmes lives in room $n$. Please help Huasheng reach room $n$ as fast as possible to find Holmes. ------ Negative modulo: if $x0$, then the result of $x \bmod p$ equals the result of $(x+p) \bmod p$. $754974721$ is a prime number.

The first line contains two positive integers $n,m$. The next $m$ lines each contain three positive integers $u_i,v_i,w_i$, describing an edge.

Output one positive integer, the shortest distance to reach room $n$.

### Sample #1 Explanation Along the path $1\rightarrow 4\rightarrow5$, the path length is $78888+150994944 = 151073832$. --- For $30\%$ of the testdata, $n\le 10$. For another $30\%$ of the testdata, all edge weights are equal. For $100\%$ of the testdata, $1\le n,m\le 10^5$. The graph is guaranteed to be connected, $1\le u_i,v_i\le n$, $1