You're trapped in a scorching dungeon with \(N\) rooms numbered from \(1\) to \(N\) connected by \(M\) tunnels. The \(i\)-th tunnel connects rooms \(a_i\) and \(b_i\) in 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 \(0\). In order to step through lava with
temperature \(\ell\), your boots must
have the same chilling level \(\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 \(d\) for a cost of \(d\) coins. You start in room \(1\) and would like to reach the exit which
you know is located in room \(N\). What
is the minimum cost to do so?

\((1 \le N, M \le 200\,000)\)
\((1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le c_i \le 10^9)\)

The first line of input contains two integers \(N\) and \(M\) \((1 \le N, M \le 200\,000)\).

The next \(M\) lines each contain
three integers \(a_i\), \(b_i\), and \(c_i\) \((1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le c_i \le 10^9)\), describing
the \(i\)-th tunnel.

There is at most one tunnel connecting any pair of rooms, and it is
possible to reach all other rooms from room \(1\).

Output the minimum cost (in coins) to reach room \(N\) from room \(1\).

생성자가 기록되지 않았습니다.

출처 CCC 2025 Senior