题目背景
译自 CCC 2025 Senior T4。本题满分为 15。
题目描述
你被困在一个炽热的地牢中。
地牢由 n 个房间组成,房间编号 1∼n。这些房间通过 m 条双向隧道相连,第 i 条双向隧道连接房间 ai 和 bi,且地板被温度为 ci 的熔岩覆盖。
为了穿越熔岩隧道,你穿着一双耐热靴子,初始冷却等级为 0。当你经过温度为 c 的熔岩时,靴子的冷却等级必须恰好为 c,否则会被烫伤/冻伤。
幸运的是,当你站在一个房间里时,你可以调整靴子的冷却等级,每次增加或减少 d 需要支付 d 枚金币。
你从房间 1 出发,目标是到达房间 n。到出口所需的最小金币花费是多少?
输入格式
第一行,两个正整数 n,m。
接下来 m 行,每行三个正整数 ai,bi,ci。
数据保证:任意一对房间之间只有至多一条隧道,从房间 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→2→3→4→5 的路线花费为 ∣3−0∣+∣2−3∣+∣3−2∣+∣4−3∣=9,可以证明是最优的。
子任务
对于 100% 的数据,保证:
- 1≤n,m≤2×105;
- 1≤ai,bi≤n;
- ai=bi;
- 1≤ci≤109;
- 任意一对房间之间只有至多一条隧道;
- 从房间 1 可以到达任意一个其他的房间。
- Subtask 0(0 points):样例。
- Subtask 1(2 points):m=n−1。
- Subtask 2(4 points):1≤ci≤10。
- Subtask 3(4 points):每个房间至多连着 5 条隧道。
- Subtask 4(5 points):无特殊限制。