AT_agc045_e [AGC045E] Fragile Balls

我们有$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.

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