题目描述

一条直线上有 $N$ 个点，从 $1$ 到 $N$ 依次编号。 高桥决定以这些点为顶点构建一个无向图。最初，图中没有边，但他通过 $m$ 次操作添加了边。第 $i$ 次操作添加边的过程如下：

给出整数 $L_i,R_i\in[1,N]$ 和 $C_i\in\N_+$。对于每一对整数 $(s,t)$ 满足 $L_i \le s < t \le R_i$，在顶点 $s$ 和顶点 $t$ 之间添加一条长度为 $C_i$ 的边。

$L_1$,...,$L_M$,$R_1$,...$R_M$，$C_1$，... ,$C_M$ 都在输入中给出。高桥希望在最终得到的图形上求解最短路径问题：求图中从顶点 $1$ 到顶点 $N$ 的最短路径长度。

输入格式

通过标准输入法输入，格式如下

$N$ $M$

$L_1$ $R_{1}$ $C_{1}$

$\vdots$ $\vdots$ $\vdots$

$L_m$ $R_{m}$ $C_m$

输出格式

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

说明/提示

$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$

样例1解释

顶点 $1$ 和顶点 $2$ 之间有一条长度为 $2$ 的边，顶点 $2$ 和顶点 $4$ 之间有一条长度为 $3$ 的边，因此顶点 $1$ 和顶点 $4$ 之间有一条长度为 $5$ 的路径。