AT_arc212_b [ARC212B] Stones on Grid

有一个 $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$ 列所放石子的数量。

输入由标准输入给出，格式如下： > $N\ M$ > $x_1\ y_1\ c_1$ > $x_2\ y_2\ c_2$ > $\vdots$ > $x_M\ y_M\ c_M$

如果无法达成目标，输出 `-1`。如果可以，请输出实现目标的最小总花费。

### 样例解释1 可以通过在第 1、2、5 次操作中各放一个石子来达成目标。 此时总花费为 $5+2+4=11$。为了实现目标，无法做到比 $11$ 更少，因此输出为 $11$。 ### 样例解释2 你必须在第 1 次操作中放一颗石子。 ### 题目约束 - $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)$ 两两不同。 - 所有输入均为整数。 由 ChatGPT 5 翻译