题目描述

$1$ から $N$ までの番号の付いた $N$ 個の箱があります． また，$1$ から $M$ までの番号の付いた $M$ 個のボールがあります． 現在，ボール $i$ は箱 $A_i$ に入っています．

あなたは，以下の操作を行えます．

• 現在ボールが $2$ 個以上入っている箱を $1$ つ選ぶ． そして，その箱からボールを $1$ つ選んで取り出し，別の箱に入れる．

ただし，ボールは非常に壊れやすいため，ボール $i$ は合計で $C_i$ 回より多く移動させることはできません． 逆に，ボールが壊れない限り，何度でもボールの移動は行なえます．

あなたの目標は，すべての $i$ ($1\ \leq\ i\ \leq\ M$)について，ボール $i$ が箱 $B_i$ に入っているようにすることです． この目的が達成可能かどうか判定してください． また可能な場合は，目標を達成するのに必要な操作回数の最小値を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

目標が達成不可能な場合は $-1$ を，達成可能な場合は必要な操作回数の最小値を出力せよ．

题目大意

题目描述

我们有$n$个盒子和$m$个球(编号都从$1$开始)，目前，球$i$在$A_i$盒子中。

接下来，对于每次操作，你可以执行以下几个操作中的一个：

• 选择一个装有两个或更多球的盒子，从中拿出一个球，把它放入另一个盒子当中
• 由于球都是易碎的，因此，你总共不能移动球$i$超过$C_i$次。

你现在的目标是对于每个$i$，将球$i$放入盒子$B_i$中。请确定这个目标是否可以实现，如果可以，则输出最少需要操作的次数，如果不可以，则输出-1。

输入格式

第一行输入两个数字$n,m$，表示盒子和球的数量。

接下来$m$行，每行三个数字$A_i,B_i,C_i$，表示第$i$个球最初始的位置，需要到达的目标位置，能够最多移动的次数。

输出格式

如果有解，则输出最少需要操作的次数，如果无解，则输出-1.

3 3
1 2 1
2 1 1
1 3 2

3

2 2
1 2 1
2 1 1

-1

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

6

1 1
1 1 1

0

提示

制約

• $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$
• 目標とする状態において，どの箱にも $1$ つ以上のボールが入っている． つまり，すべての $i$ ($1\ \leq\ i\ \leq\ N$) について，$B_j=i$ を満たす $j$ が存在する．

Sample Explanation 1

以下のように $3$ 回の操作を行えば良いです． - 箱 $1$ からボール $1$ を取り出し，箱 $2$ に入れる． - 箱 $2$ からボール $2$ を取り出し，箱 $1$ に入れる． - 箱 $1$ からボール $3$ を取り出し，箱 $3$ に入れる．