Bobo 居住在大城市 ICPCCamp，众所周知，换乘线路很麻烦，如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费。∣ 分钟，注意，换乘只能在地铁站内进行，Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
Bobo 居住在大城市 ICPCCamp。 ICPCCamp 有 n 个地铁站，用 1, 2, dots, n 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 c_i c i 号线，位于站 a_i, b_i a i ,b i 之间，往返均需要花费 t_i t i 分钟（即从 a_i a i 到 b_i b i 需要 t_i t i 分钟，从 b_i b i 到 a_i a i 也需要 t_i t i 分钟）。 众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |c_i - c_j| ∣c i −c j ∣ 分钟。注意，换乘只能在地铁站内进行。 Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
（图片来源网络，侵删）
