B - Stones on Grid 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 行 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と呼びます。 あなたは i=1,2,\ldots,M の順に以下を行います。

  • 操作 i : マス (x_i, y_i) に石を 1 つ置くか、石を置かないかどちらかを選ぶ。石を置いた場合はコストが 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

Score : 500 points

Problem Statement

There is a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is called cell (i,j). You perform the following in order of i=1,2,\ldots,M:

  • Operation i : Choose either to place one stone on cell (x_i, y_i) or not. If you place a stone, a cost of c_i is incurred; otherwise, no cost is incurred.

However, you must place a stone in operation 1.

Determine whether the following goal can be achieved, and if it can, find the minimum sum of costs incurred.

  • Goal : For every i \ (1 \leq i \leq N), the number of stones placed in the i-th row is equal to the number of stones placed in the i-th column.

Constraints

  • 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) are distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If it is impossible to achieve the goal, output -1. If it is possible, output the minimum sum of costs incurred.

Sample Input 1

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

Sample Output 1

11

The goal can be achieved by choosing to place a stone in operations 1,2,5.

The sum of costs in this case is 5+2+4=11. The total cost cannot be less than 11 to achieve the goal, so the answer is 11.

Sample Input 2

3 3
1 1 1000000000
2 2 100000000
3 3 10000000

Sample Output 2

1000000000

You must place a stone in operation 1.

Sample Input 3

2 1
1 2 10

Sample Output 3

-1