题目背景

译自 CCC 2025 Senior T4。本题满分为 $15$。

题目描述

你被困在一个炽热的地牢中。

地牢由 $n$ 个房间组成，房间编号 $1\sim n$。这些房间通过 $m$ 条双向隧道相连，第 $i$ 条双向隧道连接房间 $a_i$ 和 $b_i$，且地板被温度为 $c_i$ 的熔岩覆盖。

为了穿越熔岩隧道，你穿着一双耐热靴子，初始冷却等级为 $0$。当你经过温度为 $c$ 的熔岩时，靴子的冷却等级必须恰好为 $c$，否则会被烫伤/冻伤。

幸运的是，当你站在一个房间里时，你可以调整靴子的冷却等级，每次增加或减少 $d$ 需要支付 $d$ 枚金币。

你从房间 $1$ 出发，目标是到达房间 $n$。到出口所需的最小金币花费是多少？

输入格式

第一行，两个正整数 $n,m$。

接下来 $m$ 行，每行三个正整数 $a_i,b_i,c_i$。

数据保证：任意一对房间之间只有至多一条隧道，从房间 $1$ 可以到达任意一个其他的房间。

输出格式

输出一行一个非负整数，表示答案。

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

9

提示

样例解释

地牢的构造如上图所示。

按照 $1\to 2\to 3\to 4\to 5$ 的路线花费为 $|3-0|+|2-3|+|3-2|+|4-3|=9$，可以证明是最优的。

子任务

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 2\times 10^5$；
• $1\le a_i,b_i\le n$；
• $a_i\neq b_i$；
• $1\le c_i\le 10^9$；
• 任意一对房间之间只有至多一条隧道;
• 从房间 $1$ 可以到达任意一个其他的房间。

---

• $\text{Subtask 0(0 points)}$：样例。
• $\text{Subtask 1(2 points)}$：$m=n-1$。
• $\text{Subtask 2(4 points)}$：$1\le c_i\le 10$。
• $\text{Subtask 3(4 points)}$：每个房间至多连着 $5$ 条隧道。
• $\text{Subtask 4(5 points)}$：无特殊限制。