← 返回题目列表

AtCoder · arc212_b

B. 网格上的石头

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

分数: 500 点

问题陈述

有一个网格 N 行和 N 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列称为单元格 (i,j)。 您按以下顺序执行以下操作 i=1,2,\ldots,M:

  • 操作 i :选择在单元格上放置一颗石头 (x_i, y_i) 或不。如果放置一块石头,则需要花费 c_i 已产生;否则,不会产生任何费用。

但是, 你必须在操作中放置一块石头 1.

判断下列目标是否可以实现,如果可以,求所产生的成本之和最小。

  • 目标:对于每个 i \ (1 \leq i \leq N),放置在棋子中的棋子数量 i- 第行等于放置在 i- 第列。

约束

  • 1 \le N, M \le 2 \times 10^5
  • 1 \le x_i, y_i \le N
  • 1 \le c_i \le 10^9
  • (x_i, y_i) 是不同的。
  • 所有输入值均为整数。

输入

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

N M
x_1 y_1 c_1
x_2 y_2 c_2
\vdots
x_M y_M c_M

输出

如果无法达到目标,则输出 -1。 如果可能,输出所发生的成本的最小总和。


示例输入 1

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

示例输出 1

11

行动中选择放置石头即可实现目标 1,2,5.

这种情况下的成本总和是 5+2+4=11。总成本不能低于 11 达到目标,所以答案是 11.


示例输入 2

3 3
1 1 1000000000
2 2 100000000
3 3 10000000

示例输出 2

1000000000

你必须在操作中放置一块石头 1.


示例输入 3

2 1
1 2 10

示例输出 3

-1