Increase the Toll Fees

Time limit2sMemory limit1024 MB

Summary

Given a weighted graph with a unique minimum spanning tree, find the least total increase in tree edge prices so that no original tree edge stays in the new MST, or report -1.

Level: Medium7 of 10
Topics: Minimum spanning tree, Union-find, Tree
Solved: No attempts yet

Problem

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. To promote those sceneries, the King of the ICPC Kingdom decided to build $M$ toll roads, numbered from $1$ to $M$ , near the scenic views for tourists to enjoy. To use toll road $i$ , which 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.

The toll roads have been built and can be used, but they still do not attract tourists. The King made a promotion: one can pay in advance for the toll roads they want to use, and can use them multiple times as long as they do not leave the ICPC Kingdom.

This idea finally attracts tourists, but a strange behavior happens. Every tourist pays only for the set of toll roads with the minimum total pay that lets them travel from any city to any other city. Such a set is unique under the current toll prices. This strange behavior does not fully expose the kingdom's scenery to the tourists.

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

The King asked you to calculate the minimum total price increase that fulfills the King's plan, or to report that the plan is impossible.

Input

Input begins with two integers $N$ and $M$ ( $2 \le N \le 100\,000$ ; $N - 1 \le M \le 200\,000$ ), the number of cities and toll roads. Each of the next $M$ lines contains three integers $U_i$ , $V_i$ , $W_i$ ( $1 \le U_i < V_i \le N$ ; $1 \le W_i \le 10^9$ ), meaning toll road $i$ connects city $U_i$ and $V_i$ with price $W_i$ . Before the price increase, there is a unique set of toll roads that allows travel between any two cities with the minimum total pay.

Output

If the King's plan can be achieved, output one integer: the minimum total increase. Otherwise, output -1 on a single line.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3 4
1 2 3
2 3 4
1 3 5
1 3 10
```
Expected output
```
-1
```

Example 3

Input

Expected output