区间约束

题目描述

变量 $x_1..x_n$ 为非负整数，约束形如 $x_u - x_v \ge c$。判断是否有解；若有解输出一组解中 $\sum x_i$ 的最小值？——简化并明确化：求所有可行解中 $\max x_i$ 的最小可能值（全零起点跑最长路）。

输入格式

第一行三个整数 $n, m$（约束条数）；接下来 $m$ 行每行 u v c。另有隐式约束 $x_i - x_0 \ge 0$（$x_0=0$ 虚拟源，即 $x_i \ge 0$）。

输出格式

无解输出 -1；有解输出 $\max x_i$ 在"每个 $x_i$ 取满足约束的最小值"意义下的值（从 0 开始做最长路后取最大）。

数据范围