题目描述

有一张有 $N$ 个点，编号为 $1 - N$ 的无向图。

做 $M$ 次操作，每次操作给出三个正整数 $L,R,C$，对于每对 $≥L$ 且 $≤R$ 的整数对 $(S,T)$，在 $(S,T)$ 之间添加一条长度为 $C$ 的边。

完成操作后，找出操作后无向图的 $1$ 到 $n$ 的最短路。

输入格式

第一行为 $N,M(1\le N,M\le 10^5)$。

接下来 $M$ 行，每行 $L,R,C(1\le C\le 10^9)$ 表示一个操作。

输出格式

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