AT_arc212_b [ARC212B] Stones on Grid

$ 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 $ 列目に置かれた石の数が等しい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ $ \vdots $ $ x_M $ $ y_M $ $ c_M $

目標を達成することが不可能なら `-1` と出力せよ。 達成できる場合はかかるコストの和の最小値を出力せよ。

### Sample Explanation 1 操作 $ 1,2,5 $ で「石を置く」を選ぶことで、目標を達成することができます。 このときのコストの和は $ 5+2+4=11 $ となります。目標を達成するためにコストを $ 11 $ 未満にすることはできないため、答えは $ 11 $ です。 ### Sample Explanation 2 操作 $ 1 $ では必ず石を置くという条件に従う必要があります。 ### 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) $ は相異なる - 入力される値は全て整数