分数: 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