题目背景

实验室的天平坏了，只剩下能比较左右轻重的托盘。师兄把 $n$ 个砝码摆开，凭记忆写下 $m$ 句话，每句都断言「第 $u$ 个砝码恰好比第 $v$ 个砝码重 $d$ 克」。他说的话未必句句为真。你想知道：这些断言能不能同时成立；如果能，最少还需要真正称出几个砝码的重量，才能把全部 $n$ 个砝码的重量都算出来。

题目描述

给定 $n$ 个砝码与 $m$ 条断言，第 $i$ 条断言为 $w_u - w_v = d_i$，其中 $w_x$ 表示第 $x$ 个砝码的重量。若这 $m$ 条断言不能同时成立，输出 $-1$；否则输出一个整数，表示最少需要事先精确称出的砝码个数，使得其余砝码的重量都能由这些断言唯一确定。

输入格式

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

接下来 $m$ 行，每行三个整数 $u, v, d$。

输出格式

若断言互相矛盾，输出一行 -1；否则输出一行一个整数，表示最少需要事先精确称出的砝码个数。

输入输出样例 #1

输入 #1

3 2
1 2 5
2 3 3

输出 #1

1

输入输出样例 #2

输入 #2

2 0

输出 #2

2

输入输出样例 #3

输入 #3

3 3
1 2 1
2 3 1
1 3 5

输出 #3

-1

说明

样例解释

样例 1：由前两条断言可知 $w_2 = w_1 - 5$、$w_3 = w_2 - 3$，只要称出 $w_1$，另外两个重量就都确定了，故答案为 $1$。

样例 2：没有任何断言，每个砝码的重量都必须单独称出来，故答案为 $2$。

样例 3：前两条断言推出 $w_3 = w_1 - 2$，与第三条断言 $w_3 = w_1 - 5$ 矛盾，故输出 $-1$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n, m \le 100$；
• 对于 $60\%$ 的数据，$1 \le n, m \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^{5}$，$1 \le u, v \le n$，$|d| \le 10^{9}$。允许多条断言描述同一对砝码，也允许 $u = v$。