Dynamic Maze with Modular Road Transformations

In this problem, you are given a maze with ( n ) rooms and ( m ) bidirectional roads. The ( i )-th road connects rooms ( u_i ) and ( v_i ) with an initial length ( w_i ). The maze is magical: every time you traverse a road (i.e. every time you arrive at a room via a road), all roads change their length using the transformation [ f(t)=\frac{1}{1-t} \bmod 754974721. ] In other words, if a road currently has length ( t ), after you pass through any road, its new length becomes ( f(t) ). Note that by a quick computation one may verify that [ f^{(3)}(t)=f(f(f(t)))=t, \quad \text{for all valid } t, ] so the transformation is periodic with period 3. Thus if an edge with original weight ( w ) is used at a step where the number of roads already taken is congruent to ( r ) modulo 3, its effective cost is given by

• For ( r=0 ): ( F_0(w)=w ).
• For ( r=1 ): ( F_1(w)=\frac{1}{1-w} \bmod 754974721 ).
• For ( r=2 ): ( F_2(w)=\frac{w-1}{w} \bmod 754974721 ).

Initially, all roads are in state ( w_i ). Peanut starts at room 1 and has calculated that his elusive target, Holmes, is in room ( n ). Help Peanut find the minimum total travel cost to reach room ( n ). The total cost is computed as the sum (in usual integer arithmetic) of the effective costs of the roads taken. If room ( n ) is unreachable, output -1.

Note on modulo operations with negative numbers: For ( x < 0 ) and a positive modulus ( p ), the value of ( x \bmod p ) is defined as ( (x+p) \bmod p ).

It is guaranteed that 754974721 is a prime number, and that the input values are such that no division by zero occurs.

inputFormat

The first line contains two integers ( n ) and ( m ) (2 ( \leq n ) and ( m \ge 1)). Each of the following ( m ) lines contains three integers ( u_i, v_i, w_i ) indicating that there is a bidirectional road connecting rooms ( u_i ) and ( v_i ) with initial length ( w_i ). It is guaranteed that all computations of inverses are valid (i.e. no division by zero occurs during the transformation).

outputFormat

Output a single integer—the minimum total travel cost to reach room ( n ) from room 1. If room ( n ) is unreachable, output -1.

sample

3 2
1 2 2
2 3 3

377487362