Problem Statement

You are given an integer $N$ and length-$M$ integer sequences $L=(L_1,L_2,\dots,L_M)$, $R=(R_1,R_2,\dots,R_M)$, and $S=(S_1,S_2,\dots,S_M)$.

Determine whether there exists a length-$N$ positive integer sequence $A$ satisfying the following condition. If such a sequence exists, find the minimum possible sum of $A$.

• $\displaystyle \sum_{j=L_i}^{R_i} A_j = S_i$ for all $i$ ( $1 \le i \le M$ ).

Constraints

• All input values are integers.
• $1 \le N,M \le 4000$
• $1 \le L_i \le R_i \le N$
• $1 \le S_i \le 10^9$

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1 S_1
L_2 R_2 S_2
\vdots
L_M R_M S_M

Output

If there does not exist a length-$N$ positive integer sequence $A$ satisfying the condition, print -1. Otherwise, print the minimum possible sum of $A$ as an integer.