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.