Problem Description

Score: $ 300 $ points

To participate in the study camp, a consent form from a guardian is required. Each participant must submit one consent form.

This year, $ N $ people are participating in the study camp. Each participant is assigned a number from $ 1 $ to $ N $.

According to Rho, for $i=1, 2, \ldots, M$, the following holds:

• Among the participants $l_i, l_i+1, \ldots, r_i$, $ x_i $ people have already submitted their consent forms.

Determine if there is no contradiction in Rho's statement. If there is no contradiction, find the maximum number of people who have already submitted their consent forms.

Input Format

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

\(N\) \(M\)
\(l_1\) \(r_1\) \(x_1\)
\(l_2\) \(r_2\) \(x_2\)
\(⋮\)
\(l_M\) \(r_M\) \(x_M\)

Output Format

If there is no contradiction in Rho's statement, output the maximum number of people who have already submitted their consent forms. If there is a contradiction, output $ -1 $. Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 2
1 2 1
1 1 0

Sample Output #1

2

Sample Input #2

4 2
1 3 0
1 2 1

Sample Output #2

-1

Sample Input #3

5 2
1 3 2
3 4 2

Sample Output #3

4

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分