P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

译自 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$ 可以到达任意一个其他的房间。

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

#### 样例解释  地牢的构造如上图所示。 按照 $1\to 2\to 3\to 4\to 5$ 的路线花费为 $|3-0|+|2-3|+|3-2|+|7-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)}$：无特殊限制。