Sabotaging the Marathon Training

Sanggeun and Seonyeong are training for a marathon. Today they want to plan a training route.

Their country has $N$ cities and $M$ roads. Every road connects two cities and can be traveled in both directions. Exactly $N-1$ of the roads are paved and the rest are unpaved.

Using only paved roads you can still travel from any city to any other city; that is, the $N$ cities together with the $N-1$ paved roads form a tree. Also, every city is connected to at most $10$ roads.

A training route starts at some city, travels along several roads, and ends back at the starting city. Because the two runners want to enjoy the scenery, they never pass through a city they have already visited and never reuse a road they have already used. In other words, a training route is a single simple cycle. The starting city can be any city, and they do not have to visit every city.

Running behind the other runner is easier, because the front runner blocks the wind. So each time they enter a city the two runners swap the front and back positions. To keep their training equal, the number of roads they traverse must be even. Therefore a valid training route is a simple cycle that uses an even number of roads.

Their rivals Sangdeok and Heewon want to make sure no such training route can exist, so they will blow up some of the unpaved roads. The cost (a positive integer) of blowing up each unpaved road is given, and paved roads cannot be blown up.

Given the cities and roads, find the minimum total cost needed so that no valid training route remains.

The first line contains the number of cities $N$ and the number of roads $M$. ($2 \le N \le 1{,}000$, $N-1 \le M \le 5{,}000$)

Each of the next $M$ lines contains three integers $A$, $B$, and $C$. ($1 \le A, B \le N$, $0 \le C \le 10{,}000$) $A$ and $B$ are distinct and denote the two cities joined by the road. If $C = 0$ the road is paved; if $C > 0$ the road is unpaved and $C$ is the cost of blowing it up.

Every city is connected to at most $10$ roads, and there is at most one road between any pair of cities.

Print, on the first line, the minimum total cost required so that no valid training route remains.

In the first example there are five routes that satisfy the training conditions. Blowing up the unpaved roads $1$–$3$, $3$–$5$, and $2$–$5$ removes all of them, at a cost of $2 + 2 + 1 = 5$. Blowing up roads $2$–$4$ and $2$–$5$ also works, but costs $5 + 1 = 6$, which is more. Hence the minimum cost is $5$.