Problem Description

The ICPC Kingdom is a big kingdom with $N$ cities, numbered from $1$ to $N$. The charm of the ICPC Kingdom lies in its beautiful sceneries in the kingdom. To promote those sceneries, the King of the ICPC Kingdom decided to make $M$ toll roads, numbered from $1$ to $M$, near the scenic views for the tourists to enjoy. To use toll road $i$ that connects city $U_i$ to $V_i$ bidirectionally, one must pay $W_i$. It is possible to travel from one city to any other city using these toll roads.

Although those toll roads have been built and can be used, they still do not attract tourists. The King decided to make a promotion, where one can pay in advance for the toll roads they want to use and can use it multiple times as long as they do not leave the ICPC Kingdom.

This idea can finally attract tourists, but there's a strange behaviour happening. All of the tourists only pay for the set of toll roads that gives the minimum total pay which allows them to travel from one city to any other city regardless of the distance. Interestingly, such a set of toll roads is unique under current toll pricing. This strange behaviour does not fully expose the kingdom's scenery to the tourists.

To promote more scenery, the King decided to increase the price of some toll roads. If toll road $i$ is used by the tourists' strange behaviour before the toll price increase, then after the price increase, the King must ensure toll road $i$ is not used by the tourists' strange behaviour. For stability, the King also wants the total price increase across all toll roads to be as small as possible.

The King asked you to calculate what is the minimum total price increase to fulfill the King's plan or report that it is impossible to do so.

Input Format

Input begins with two integers $N$ $M$ ($2 \leq N \leq 100\,000$; $N-1 \leq M \leq 200\,000$) representing the number of cities and toll roads. Each of the next $M$ lines contains $3$ integers $U_i$ $V_i$ $W_i$ ($1 \leq U_i < V_i \leq N$; $1 \leq W_i \leq 10^9$) representing toll $i$ that connects city $U_i$ and $V_i$ with price $W_i$. There exists a unique set of toll roads that allow travel between any two cities with minimum total pay before the price increase.

Output Format

If the King's plan is possible to achieve, then output an integer representing the minimum total increase to fulfill the King's plan. Otherwise, output $-1$ in a single line.

4 6
1 2 2
1 3 5
1 4 5
2 3 3
2 4 5
3 4 4

9

3 4
1 2 3
2 3 4
1 3 5
1 3 10

-1

5 10
1 2 14
1 3 14
1 4 9
1 5 15
2 3 8
2 3 10
2 4 13
3 4 8
4 5 10
4 5 15

21

Hint

Explanation for the sample input/output #1

Before the price increase, the tourists will choose toll roads $1$, $4$, and $6$ to travel. By increasing the price of toll roads $1$, $4$, and $6$, to $6$, the tourists will use toll roads $2$, $3$, and $5$ to travel. Total increase toll roads is $(6 - 2) + (6 - 3) + (6 - 4) = 9$.

Explanation for the sample input/output #2

Before the price increase, the tourists will choose toll roads $1$ and $2$. No matter how many the price increase, the tourists will always choose at least one of those two toll roads.