IOI '07 - Zagreb, Croatia
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. Every road connects two cities and can be traversed in both
directions. Exactly
of those roads are paved, while the rest of the roads are unpaved trails. Fortunately, the
network of roads was designed so that each pair of cities is connected by a path consisting of paved roads. In
other words, the
cities and the
paved roads form a tree structure.
Additionally, each city is an endpoint for at most roads total.
A training route starts in some city, follows some roads and ends in the same city it started in. Mirko and Slavko like to see new places, so they made a rule never to go through the same city nor travel the same road twice. The training 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 rider in the front. Because of this, Mirko and Slavko change seats in every city. To ensure that they get the same amount of training, they must choose a route with an even number of roads.
Mirko and Slavko's competitors decided to block some of the unpaved roads, making it impossible for them to find a training route satisfying the above requirements. For each unpaved road there is a cost (a positive integer) associated with blocking the road. It is impossible to block paved roads.
Write a program that, given the description of the network of cities and roads, finds the smallest total cost needed to block the roads so that no training route exists satisfying the above requirements.
Input Specification
The first line of input contains two integers and
, the number of cities
and the total number of roads.
Each of the following lines contains three integers
,
and
,
describing one road. The numbers
and
are different and they represent the cities directly connected by the
road. If
, the road is paved; otherwise, the road is unpaved and
represents the cost of blocking it.
Each city is an endpoint for at most roads. There will never be more than one road directly connecting a
single pair of cities.
Output Specification
Output should consist of a single integer, the smallest total cost as described in the problem statement.
Grading
In test cases worth a total of points, the paved roads will form a chain (that is, no city will be an endpoint for
three or more paved roads).
Sample Input 1
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
Sample Output 1
5
Explanation for Sample Output 1
The layout of the roads and cities in the first example. Paved roads are shown in bold.
There are five possible routes for Mirko and Slavko. If the roads ,
and
are blocked, then Mirko and Slavko
cannot use any of the five routes. The cost of blocking these three roads is
.
It is also possible to block just two roads, and
, but this would result in a higher cost of
.
Sample Input 2
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0
Sample Output 2
48
Comments