题目描述

冷库里有 $n$ 个温控探头，第 $i$ 个探头的读数为整数 $t_i$。

校准记录中有 $m$ 条关系，第 $j$ 条形如「$t_v$ 至少比 $t_u$ 高 $c$」或「$t_v$ 至多比 $t_u$ 高 $c$」，用 $t_j$ 区分：

• $t_j=0$：$t_v-t_u\ge c$；
• $t_j=1$：$t_v-t_u\le c$。

$c$ 可以为负数，表示「低 $|c|$ 度」。

请判断是否存在满足全部关系的整数读数：

• 若关系互相矛盾，输出 $-1$；
• 若存在满足关系的读数，但 $t_n-t_1$ 可以任意大，输出 $-2$；
• 否则输出 $t_n-t_1$ 的最大可能值。

输入格式

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

接下来 $m$ 行，每行四个整数 $u,v,c,t$，含义如上。保证 $1\le u,v\le n$，$u\ne v$。

输出格式

一行一个整数，含义见题面。

输入输出样例 #1

输入 #1

3 3
1 2 0 0
2 3 0 0
1 3 5 1

输出 #1

5

输入输出样例 #2

输入 #2

2 2
1 2 1 0
1 2 0 1

输出 #2

-1

输入输出样例 #3

输入 #3

3 1
1 2 0 0

输出 #3

-2

说明

样例 $1$ 中 $t_2\ge t_1$，$t_3\ge t_2$，$t_3\le t_1+5$，故 $t_3-t_1$ 最大为 $5$。

数据范围

• 对于 $100\%$ 的数据，$2\le n\le 1000$，$0\le m\le 5000$，$|c|\le 10^9$。