Minimum Rescue Repair Time

After the 4.20 Sichuan Lushan earthquake, the Rescue Committee was assigned an urgent task. The provincial map provided a description of some cities in the province. Any two cities are connected by one or more bidirectional roads, or not directly connected at all; however, every city is reachable from every other city (possibly indirectly). Due to aftershocks and heavy rain causing landslides, driving on these roads has become very unsafe. Therefore, the province decided to quickly repair a subset of roads to ensure that the rescue vehicles can travel safely.

The map records the time required to repair each road. The task is to select a set of roads to repair such that:

1. After repair, any two cities remain connected (i.e. the induced subgraph is connected);
2. Even if any one repaired road is blocked by a landslide, the connectivity between any two cities is still maintained. In other words, the repaired road network must be 2-edge-connected (i.e. it has no bridges).
3. The total repair time is minimized.

You are given a graph with n cities (numbered 1 through n) and m roads. Each road connects two cities and has an associated repair time. If there is no way to choose such a subset of roads, output -1.

Note: A graph is 2-edge-connected if it remains connected after removal of any one edge. In mathematical terms, for every edge e in the chosen set, the graph \(G\setminus\{e\}\) is connected.

inputFormat

The first line contains two integers n and m representing the number of cities and roads respectively.

The following m lines each contain three integers u, v, and cost, indicating that there is a bidirectional road between city u and city v that requires cost time to repair.

outputFormat

Output the minimum total repair time of a set of roads satisfying the conditions. If no such set exists, output -1.

sample

3 3
1 2 1
2 3 1
1 3 3

5