← 返回题目列表

AtCoder · agc045_e

E. 易碎球

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

我们有 N 盒子编号 1 to N,和 M 球编号 1 to M。 目前,鲍尔 i 装在盒子里 A_i.

您可以执行以下操作:

  • 选择一个包含两个或多个球的盒子,从该盒子中拿起其中一个球,然后将其放入另一个盒子中。

由于球很容易损坏,因此您无法移动球 i 超过 总共 C_i 次。 在此限制内,您可以执行任意次数的操作。

你的目标是拥有鲍尔 盒子里的 i 盒装 B_i 对于每个 i (1 \leq i \leq M)。 确定这个目标是否可以实现。 如果是,还需要找到实现它所需的最少操作数。

约束

  • 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
  • 在达到目标的情况下,每个盒子包含一个或多个球。 也就是说,对于每一个 i (1 \leq i \leq N),存在 j 这样 B_j=i.

输入

输入由标准输入按以下格式给出:

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

输出

如果目标无法实现,则打印 -1;如果可以实现,请打印实现它所需的最少操作数。


示例输入 1

3 3
1 2 1
2 1 1
1 3 2

示例输出 1

3

我们可以通过三个操作来实现该目标,如下所示:

  • 捡球 1 来自盒子 1 并将其放入盒子中 2.
  • 捡球 2 来自盒子 2 并将其放入盒子中 1.
  • 捡球 3 来自盒子 1 并将其放入盒子中 3.

示例输入 2

2 2
1 2 1
2 1 1

示例输出 2

-1

示例输入 3

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

示例输出 3

6

示例输入 4

1 1
1 1 1

示例输出 4

0