Problem Description

There are $ N $ points on a straight line, numbered sequentially from $ 1 $ to $ N $.

Takahashi decided to create an undirected graph using these points as vertices. Initially, the graph has no edges, but he will add edges through $ M $ operations. In the $ i $-th operation, edges are added as follows:

• Using integers $ L_i $, $ R_i $ between $ 1 $ and $ N $ inclusive, and a positive integer $ C_i $. For all integer pairs $ (s, t) $ such that $L_i \leq s < t \leq R_i$, add an edge of length $ C_i $ between vertex $ s $ and vertex $ t $.

Note that $ L_1, ..., L_M $, $ R_1, ..., R_M $, and $ C_1, ..., C_M $ are all given as input.

Takahashi wants to solve the shortest path problem on the final graph. Determine the length of the shortest path from vertex $ 1 $ to vertex $ N $ on the obtained graph.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L_1 $ $ R_1 $ $ C_1 $ $ : $ $ L_M $ $ R_M $ $ C_M $

Output Format

Output the length of the shortest path from vertex $ 1 $ to vertex $ N $. If no such path exists, output -1.

Sample Input and Output

Sample Input #1

4 3
1 3 2
2 4 3
1 4 6

Sample Output #1

5

Sample Input #2

4 2
1 2 1
3 4 2

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

28

Notes/Hints

Constraints

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

Sample Explanation 1

There is an edge of length $ 2 $ between vertex $ 1 $ and vertex $ 2 $, and an edge of length $ 3 $ between vertex $ 2 $ and vertex $ 4 $. Therefore, there is a path of length $ 5 $ between vertex $ 1 $ and vertex $ 4 $.

见题面 Input 部分

见题面 Output 部分