Background

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?

Problem Description

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; 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 $x<0,p>0$, then the result of $x \bmod p$ equals the result of $(x+p) \bmod p$.

$754974721$ is a prime number.

Input Format

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 Format

Output one positive integer, the shortest distance to reach room $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

Hint

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<w_i<754974721$, and it is guaranteed that at any moment there will never be an edge with weight $1$.

All input numbers are integers.

Postscript:
After Huasheng arrived at the room where Holmes lived, he saw Holmes staring at the screen without blinking. “What are you looking at?”
Holmes: “I don’t know.”

Translated by ChatGPT 5