You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 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)}$：无特殊限制。