Escape from the Fiery Dungeon

You are trapped in a blazing dungeon consisting of $n$ rooms numbered $1$ to $n$. The rooms are connected by $m$ bidirectional tunnels. The $i$-th tunnel connects room $a_i$ and room $b_i$, and its floor is covered with lava at temperature $c_i$.

To traverse a lava tunnel safely while wearing your heat-resistant boots, the boot’s cooling level must be (c) exactly equal to the tunnel's lava temperature. Initially, your boot’s cooling level is (0).

Fortunately, when you are in a room, you can adjust the boot’s cooling level arbitrarily. Increasing or decreasing the cooling level by (d) costs you (d) coins.

Your task is to get from room (1) to room (n) with the minimum total coin cost. Determine the minimum number of coins needed.

inputFormat

The first line contains two integers (n) and (m) (the number of rooms and tunnels). Each of the next (m) lines contains three integers (a_i), (b_i), and (c_i), indicating that there is a bidirectional tunnel between room (a_i) and room (b_i) with a lava temperature of (c_i).

outputFormat

Output a single integer: the minimum coin cost required to travel from room (1) to room (n). If it is impossible to reach room (n), output -1.

sample

3 2
1 2 5
2 3 5

5