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\le n\le 10^5$ - $1\le m\le 10^5$ - $1\le A_i,B_i\le n$ - $1\le C_i\le 10^5$