AT_agc045_e [AGC045E] Fragile Balls

[problemUrl]: https://atcoder.jp/contests/agc045/tasks/agc045_e $ 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 $ を，達成可能な場合は必要な操作回数の最小値を出力せよ．

### 制約 - $ 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 $ に入れる．