题目描述

我们有 $N$ 个编号为 $1$ 到 $N$ 的盒子，和 $M$ 个编号为 $1$ 到 $M$ 的球。初始时，球 $i$ 放在盒子 $A_i$ 中。

你可以进行以下操作：

• 选择一个包含两个或更多个球的盒子，从中取出一个球，并将其放入另一个盒子中。

由于球很容易损坏，你不能让球 $i$ 移动超过 $C_i$ 次。在这个限制下，你可以进行任意次数的操作。

你的目标是让所有球 $i$（$1 \\leq i \\leq M$）都放在盒子 $B_i$ 中。判断是否能够实现这个目标。如果能够实现，还需找到实现它所需的最小操作次数。

约束条件

• $1 \\leq N \\leq 10^5$
• $1 \\leq M \\leq 10^5$
• $1 \\leq A_i,B_i \\leq N$
• $1 \\leq C_i \\leq 10^5$
• 在目标实现的情况下，每个盒子都至少包含一个球。也就是说，对于每个 $i$（$1 \\leq i \\leq N$），存在 $j$，使得 $B_j=i$。

输入

输入以标准输入格式给出，格式如下所示：

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\\vdots$ $A_M$ $B_M$ $C_M$

输出

如果无法实现目标，则输出 $-1$；如果能够实现目标，则输出实现它所需的最小操作次数。

示例输入 1

3 3
1 2 1
2 1 1
1 3 2

示例输出 1

3

我们可以用以下三个操作实现目标：

• 从盒子 $1$ 中取出球 $1$ 并放入盒子 $2$。
• 从盒子 $2$ 中取出球 $2$ 并放入盒子 $1$。
• 从盒子 $1$ 中取出球 $3$ 并放入盒子 $3$。

示例输入 2

2 2
1 2 1
2 1 1

示例输出 2

-1

示例输入 3

5 5
1 2 1
2 1 1
1 3 2
4 5 1
5 4 1

示例输出 3

6

示例输入 4

1 1
1 1 1

示例输出 4

0