Floor is Lava

문제

You’re trapped in a scorching dungeon with $NN$ rooms numbered from 1$$to $NN$ connected by $MM$ tunnels. The i$$-thtunnelconnectsrooms-th\; tunnel\; connects\; rooms$a_i$andand$b_i$inbothdirections,butthefloorofthetunneliscoveredinlavawithtemperaturein\; both\; directions,\; but\; the\; floor\; of\; the\; tunnel\; is\; covered\; in\; lava\; with\; temperature$c_i$.

To help you navigate the lavatic tunnels, you are wearing a pair of heat-resistant boots that initially have a chilling level of $00$. In order to step through lava with temperature $\mathrm{\ell }\backslash ell$, your boots must have the same chilling level $\mathrm{\ell }\backslash ell$; if the chilling level is too low then the lava will melt your boots, and if it’s too high then your feet will freeze as you cross the tunnel.

Luckily, when you’re standing in a room, you can increase or decrease the chilling level of your boots by $dd$ for a cost of $dd$ coins. You start in room $11$ and would like to reach the exit which you know is located in room $NN$. What is the minimum cost to do so?

입력

The first line of input contains two integers $NN$ and $MM$ (1 ≤ N, M ≤ 200\, 000).

The next $MM$ lines each contain three integers $a_{i}a\_i$, $b_{i}b\_i$, and $c_{i}c\_i$ (1 ≤ a_i , b_i ≤ N, $a_i\mathrm{\ne }{b}_{i}a\_i\; \backslash ne\; b\_i$, 1 ≤ c_i ≤ 10^9), describing the $ii$-th tunnel.

There is at most one tunnel connecting any pair of rooms, and it is possible to reach all other rooms from room $11$.

출력

Output the minimum cost (in coins) to reach room $NN$ from room $11$.

5 7
1 2 3
2 3 2
1 3 6
3 4 3
4 5 7
2 4 1
2 5 10

9