题目描述
给定 n,m,以及 m 个形如 axi≥ayi+azi(1≤i≤m) 的条件。问是否有一组正整数 (a1,a2,⋯,an) 满足所有条件,并且 a1+a2+⋯+an≤109。如果有,输出 a1+a2+⋯+an 的最小值;如果无解,输出 −1。
输入格式
从标准输入读入数据。
第一行两个整数 n,m(1≤n,m≤2×105)。
之后 m 行,第 i 行三个整数 xi,yi,zi,表示一个限制 axi≥ayi+azi(1≤xi,yi,zi≤n)。
输出格式
输出到标准输出。
输出一行一个整数,表示答案。
样例
输入
5 2
1 2 3
3 4 5
输出
8
解释
和最小的解为 (3,1,2,1,1),和为 8。