该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在“星轨走廊”中依次排列着 $N$ 个空间中继站，从左到右编号为 $1$ 到 $N$。工程师准备逐步启用若干套“群发广播协议”，使得走廊内部分中继站之间可以直接进行一次跳转通信。你需要计算从起点中继站 $1$ 向终点中继站 $N$ 发送信号的最短总耗能。

具体来说：

有 $N$ 个中继站按顺序排成一列，编号为 $1,2,\dots,N$。初始时网络中没有任何通信链路。

接下来会进行 $M$ 次协议启用操作。第 $i$ 次操作给出三个整数 $L_i, R_i, C_i$（$1 \le L_i < R_i \le N$，$C_i > 0$），表示：

• 对于所有满足 $L_i \le s < t \le R_i$ 的站点对 $(s,t)$，在站点 $s$ 与站点 $t$ 之间建立无向通信链路；
• 该链路的耗能（边权）均为 $C_i$。

所有操作完成后，求从站点 $1$ 到站点 $N$ 的最短路径耗能之和。若无法到达，输出 $-1$。

输入格式

第一行两个整数 $N, M$。

接下来 $M$ 行，每行三个整数 $L_i, R_i, C_i$，表示一次协议启用操作。

输出格式

输出一个整数，表示从站点 $1$ 到站点 $N$ 的最短路径长度；若不存在路径则输出 $-1$。

样例

4 3
1 3 2
2 4 3
1 4 6

5

4 2
1 2 1
3 4 2

-1

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

28

数据范围

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le L_i < R_i \le N$
• $1 \le C_i \le 10^9$