AT_abc404_g [ABC404G] Specified Range Sums

给你一个整数 $N$ 和 $M$ 个整数三元组 $(L_i,R_i,S_i)$。 判断是否存在一个长度为 $N$ 的**正整数**数列 $A$，满足对于所有的三元组限制 $(L_i,R_i,S_i)$，满足 $\sum\limits_{j=L_i}^{R_i}A_j=S_i$。如果存在，找出合法的 $A$ 的最小元素和。

第一行两个整数 $N,M(1\le N,M\le 4000)$。\ 接下来 $M$ 行，每行三个整数 $L_i,R_i,S_i(1\le L_i\le R_i\le N,1\le S_i\le 10^9)$。

如果不存在符合条件的 $A$，输出一个整数 $-1$。\ 否则，输出一个整数，表示合法的 $A$ 的最小元素和。

**样例 1 解释** $A=(1,3,2,1,5)$ 是一种符合条件的情况。\ 此情况下 $A$ 的和是 $12$，可以证明这是可能的最小值。 **样例 2 解释** 此时无解。 By chenxi2009