该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
数据、标程、题解等资源的获取：https://gitlink.org.cn/thusaa/gdcpc2024
题目描述
给定 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。
