Type: Default 1000ms 256MiB

[2024 GDCPC I] 不等式

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定 n,mn,m,以及 mm 个形如 axi≥ayi+azi(1≤i≤m)a_{x_i}\ge a_{y_i}+a_{z_i}(1 \le i \le m) 的条件。问是否有一组正整数 (a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n) 满足所有条件,并且 a1+a2+⋯+an≤109a_1+a_2+\cdots+a_n \le 10^{9}。如果有,输出 a1+a2+⋯+ana_1+a_2+\cdots+a_n 的最小值;如果无解,输出 −1-1。

Input

第一行两个整数 n,m(1≤n,m≤2×105)n,m(1 \le n,m \le 2\times 10^5)。

之后 mm 行,第 ii 行三个整数 xi,yi,zix_i,y_i,z_i,表示一个限制 axi≥ayi+azi(1≤xi,yi,zi≤n)a_{x_i}\ge a_{y_i}+a_{z_i}(1\le x_i,y_i,z_i \le n)。

Output

输出一行一个整数,表示答案。

5 2
1 2 3
3 4 5
8

Notes

和最小的解为 (3,1,2,1,1)(3,1,2,1,1),和为 88。