## 题目背景

小气鬼准备乘飞机去旅游。所有的航空公司联合推出了一款优惠活动，如果一张机票包含多段行程，则可以优惠掉最贵的那段行程。比如说一张机票从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}$| 无|