Training#285
Mirko and Slavko are training hard for the annual tandem cycling marathon taking place in Croatia. They need to choose a route to train on.
There are cities and roads in their country. Each road connects two cities and can be traversed in both directions. Exactly N-1 of these roads are paved, and the remaining roads are unpaved trails. Fortunately, the road network is designed so that every pair of cities is connected by a path consisting only of paved roads. In other words, the cities and the N-1 paved roads form a tree structure.
Additionally, each city is an endpoint of at most roads.
A training route starts in some city, follows a sequence of roads, and ends in the same city where it started. Mirko and Slavko enjoy seeing new places, so they made a rule: they never visit the same city or travel along the same road twice in a single route. The route may start in any city and does not need to visit every city.
Riding in the back seat is easier, since the rider is shielded from the wind by the partner in front. Therefore, Mirko and Slavko switch seats in every city. To ensure each gets the same training, they must choose a route that consists of an even number of roads.
Mirko and Slavko's competitors decided to block some of the unpaved roads so that it becomes impossible to construct a training route that satisfies the above requirements. Each unpaved road can be blocked for a positive integer cost. Paved roads cannot be blocked.
Write a program that, given the description of the network of cities and roads, finds the smallest total cost needed to block roads so that no training route exists satisfying the above requirements.
The first line contains two integers and (2 \le N \le 1000, N-1 \le M \le 5000), the number of cities and the total number of roads.
Each of the following lines describes a road with three integers , , and (1 \le A, B \le N, 0 \le C \le 10\ 000). and are distinct and represent the cities directly connected by the road. If C = 0, the road is paved; otherwise, the road is an unpaved trail and denotes the cost to block it.
Each city is an endpoint of at most roads. There is at most one road directly connecting any pair of cities.
Output a single integer: the smallest total cost as described above.
Example 1