题目描述

一家工厂要在 $n$ 个车间里依次启动设备，用 $t_i$ 表示第 $i$ 个车间的启动时刻。启动必须按照车间编号往后推进，即对每个 $1\le i<n$ 都有

除此之外，工艺上还给出了 $m$ 条要求，每条要求形如「第 $v$ 个车间至少比第 $u$ 个车间晚 $c$ 启动」，也就是

请判断这些要求能不能同时满足。如果可以，输出 $t_n-t_1$ 的最小可能值；如果要求互相矛盾（不可能同时满足），输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,c$，含义如上。

输出格式

一行一个整数，表示 $t_n-t_1$ 的最小可能值，或 $-1$。

输入输出样例 #1

输入 #1

4 3
1 2 5
2 4 3
1 3 10

输出 #1

10

说明

数据范围

• 对于 $100\%$ 的数据，$2\le n\le 2000$，$0\le m\le 10^4$，$1\le u,v\le n$，$u\ne v$，$1\le c\le 10^4$。

时刻可以取任意整数（可以为负），只要满足所有要求即可。