AT_nikkei2019_2_qual_d Shortest Path on a Line

在一条直线上有 $N$ 个点，依次编号为 $1$ 到 $N$。 高桥君打算以这些点为顶点，构建一个无向图。初始时图中没有边，通过 $M$ 次操作添加边。在第 $i$ 次操作中，按照如下方式添加边： - 给定 $1$ 到 $N$ 之间的整数 $L_i$、$R_i$ 以及正整数 $C_i$。对于所有满足 $L_i \leq s < t \leq R_i$ 的整数对 $(s, t)$，在顶点 $s$ 和顶点 $t$ 之间添加一条长度为 $C_i$ 的边。 所有的 $L_1,\ldots,L_M$，$R_1,\ldots,R_M$，$C_1,\ldots,C_M$ 都由输入给出。 高桥君想要在最终得到的图上解决最短路问题。请你求出在最终的图上，从顶点 $1$ 到顶点 $N$ 的最短路径长度。如果不存在这样的路径，则输出 $-1$。

输入以如下格式从标准输入给出。 > $N$ $M$ > $L_1$ $R_1$ $C_1$ > $\vdots$ > $L_M$ $R_M$ $C_M$

请输出从顶点 $1$ 到顶点 $N$ 的最短路径长度。如果不存在最短路径，则输出 $-1$。

### 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq M \leq 10^5$ - $1 \leq L_i < R_i \leq N$ - $1 \leq C_i \leq 10^9$ ### 样例解释 1 在顶点 $1$ 和顶点 $2$ 之间有一条长度为 $2$ 的边，在顶点 $2$ 和顶点 $4$ 之间有一条长度为 $3$ 的边，因此从顶点 $1$ 到顶点 $4$ 存在一条长度为 $5$ 的路径。 由 ChatGPT 4.1 翻译