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

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

题目背景

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

题目描述

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

地牢由 nn 个房间组成,房间编号 1n1\sim n。这些房间通过 mm双向隧道相连,第 ii双向隧道连接房间 aia_ibib_i,且地板被温度为 cic_i 的熔岩覆盖。

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

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

你从房间 11 出发,目标是到达房间 nn。到出口所需的最小金币花费是多少?

输入格式

第一行,两个正整数 n,mn,m

接下来 mm 行,每行三个正整数 ai,bi,cia_i,b_i,c_i

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

输出格式

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

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

提示

样例解释

地牢的构造如上图所示。

按照 123451\to 2\to 3\to 4\to 5 的路线花费为 30+23+32+43=9|3-0|+|2-3|+|3-2|+|4-3|=9,可以证明是最优的。

子任务

对于 100%100\% 的数据,保证:

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

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