题目背景

小气鬼准备乘飞机去旅游。所有的航空公司联合推出了一款优惠活动，如果一张机票包含多段行程，则可以优惠掉最贵的那段行程。比如说一张机票从A市先飞到B市，这段行程原价花费100元，再从B市飞到C市，这段行程原价花费100元，再从C市飞到D市，这段行程原价花费300元。如果按照这组行程购买一张票，那么可以优惠掉最贵的300元，只需要花费200元。如果是直飞的行程，不经停其他城市，则不提供优惠。当然，一组行程必须连续，上一段行程的抵达城市必须是下一段行程的起始城市。

小气鬼不是很在意反复进入机场、等待航班花费的时间、购买票的张数等等，他只关心花的钱数。他可以经停任意多个城市、也可以把总行程拆分成多组分次购票，只为花费尽可能少的钱到达目标城市。

题目描述

有n个城市，编号为1~n，小气鬼目前在1号城市，计划到n号城市去旅游。航空公司提供了m个航班，其中第i个航班是从$u{i}市出发，停留在v{i}市，售价（原价）w_{i}$元。

求小气鬼的最小花费。保证从1号城市出发至少存在一条路线可以到达n号城市。

输入的第一行包含两个数字n,m。

接下来m行，每行包含3个数字$u{i}、v{i}、w_{i}，分别表示第i$个航班的起始城市、到达城市、售价。

输出仅一个数字，是小气鬼的最小花费。

样例1解释

从城市1移动到城市3有两种不同的方案：

1->2->3。有两段行程，均花费10元，可以优惠掉其中一段，总花费为10元。

1->3。因为路线只包含一段行程，无法优惠，总花费为15元。

小气鬼选择第一种方案花费最少。

样例2解释

城市1到城市5的路线只有一条：1->2->3->4->5。小气鬼的最优方案是分两段购票，1->2->3购买一张票；3->4->5购买一张票，这两张票均是包含100元和10元的两段行程，各自优惠掉最贵的那段,总共只需要花费20元。

数据范围

对于所有测试数据有：1\leq n\leq {5\times 10}^{4},1\leq m\leq {2\times 10}^{5},$1\leq u{i},v{i}\leq n, u{i}\neq v{i}, 1\leq w{i}\leq {10}^{9}。保证从1号城市出发至少存在一条路线可以到达n号城市。 |测试点| n≤| m≤| 特殊性质| |-----|-----|-----|-----| |1~2| 10| {10}^{2}| 无| |3~4| 20| {10}^{2}| 无| |5| {10}^{2}| {10}^{3}| u{i}\lt v{i}且w{i}=1| |6~7| {10}^{2}| {10}^{3}| u{i}=v{i}-1| |8~10| {10}^{2}| {10}^{3}| 无| |11~12| {10}^{3}| {10}^{4}| w{i}=1| |13~14| {10}^{3}| {10}^{4}| u{i}=v{i}-1| |15~17|  {10}^{3}| {10}^{4}| 无| |18~19|  {10}^{4}| {10}^{5}| u{i}\lt v{i}| |20| {5\times 10}^{4}| {2\times 10}^{5}| w{i}=1| |21| {5\times 10}^{4}| {2\times 10}^{5}| u{i}=v{i}-1| |22~25| {5\times 10}^{4}| {2\times 10}^{5}$| 无|

2026第五届青少年编程挑战精英赛