配点 : $1200$ 点

問題文

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

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

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

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

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

入力

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

$N$ $M$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

出力

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

3 3
1 2 1
2 1 1
1 3 2

3

以下のように $3$ 回の操作を行えば良いです．

• 箱 $1$ からボール $1$ を取り出し，箱 $2$ に入れる．
• 箱 $2$ からボール $2$ を取り出し，箱 $1$ に入れる．
• 箱 $1$ からボール $3$ を取り出し，箱 $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