Safe Emergency Contact Network

A mountain region has $N$ villages and $M$ roads, and each road joins two villages. The roads connect every village: starting from any village you can reach every other village by following one or more roads. Two neighboring villages are sometimes joined directly by more than one road.

To pass along urgent news, the region will build an emergency contact network that connects all villages. A road in the network needs special upkeep, so every road has a maintenance cost. The network is built so that the total maintenance cost is as small as possible.

Landslides happen here, and a landslide can make one road impassable. At most one road becomes impassable.

For each road, assume that this one road is impassable and find the minimum total maintenance cost of an emergency contact network built from the remaining roads. If the remaining roads cannot connect all villages, the answer for that road is -1.

The first line has the number of villages $N$ (2 ≤ $N$ ≤ 100,000) and the number of roads $M$ (2 ≤ $M$ ≤ 300,000). Villages are numbered 1 through $N$.

Each of the next $M$ lines has three natural numbers. The first two are the numbers of the villages the road joins, and the third is the maintenance cost of that road when it belongs to the emergency contact network. A cost is between 1 and $10^9$. Several roads can join the same pair of villages, and two different roads can have the same cost.

Print $M$ lines. Line $i$ has the minimum total maintenance cost of the emergency contact network when the $i$-th road of the input is impassable. If no such network exists, print -1.

The sum of costs can exceed the range of a 32-bit integer, so a 64-bit integer may be needed.