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 $N$ cities and $M$ roads in their country. Every road connects two cities and can be traversed in both directions. Exactly $N-1$ 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 $N$ cities and the $N-1$ paved roads form a tree structure.

Additionally, each city is an endpoint for at most $10$ 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 $N$ and $M$ $(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 $M$ lines contains three integers $A$, $B$ and $C$ $(1\le A\le N,1\le B\le N,0\le C\le 10000)$, describing one road. The numbers $A$ and $B$ are different and they represent the cities directly connected by the road. If $C=0$, the road is paved; otherwise, the road is unpaved and $C$ represents the cost of blocking it.

Each city is an endpoint for at most $10$ 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 $30$ 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 $1-3$, $3-5$ and $2-5$ are blocked, then Mirko and Slavko cannot use any of the five routes. The cost of blocking these three roads is $5$.

It is also possible to block just two roads, $2-4$ and $2-5$, but this would result in a higher cost of $6$.

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