As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
给定 $n,m$，以及 $m$ 个形如 $a_{x_i}\ge a_{y_i}+a_{z_i}(1 \le i \le m)$ 的条件。问是否有一组正整数 $(a_1,a_2,\cdots,a_n)$ 满足所有条件，并且 $a_1+a_2+\cdots+a_n \le 10^{9}$。如果有，输出 $a_1+a_2+\cdots+a_n$ 的最小值；如果无解，输出 $-1$。
从标准输入读入数据。
第一行两个整数 $n,m(1 \le n,m \le 2\times 10^5)$。
之后 $m$ 行，第 $i$ 行三个整数 $x_i,y_i,z_i$，表示一个限制 $a_{x_i}\ge a_{y_i}+a_{z_i}(1\le x_i,y_i,z_i \le n)$。
输出到标准输出。
输出一行一个整数，表示答案。
5 2
1 2 3
3 4 58和最小的解为 $(3,1,2,1,1)$，和为 $8$。
The discussion section is only for posting: Editorials, General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: