TRAIN07 - Training

no tags 

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. Mirko and Slavko are training hard for the annual tandem cycling marathon taking place in Croatia. They need to 

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

 

The first line of input contains two integers N and M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000), the number of cities and the total number of roads. 

Each of the following M lines contains three integers A, B and C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000), 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

Output should consist of a single integer, the smallest total cost as described in the problem statement.

 

Example

Input:
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

Output:
5
Input:
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 
Output:
48

hide comments
:D: 2012-05-24 10:30:43

You have to block all cycles with even number of nodes, not just the cheapest one. It is clearly said in the description:
"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."

Please read the description carefully.

Casper Castle: 2012-05-24 07:52:03

You said "The training route may start in any city and does not need to visit every city. " then why input 1 got cost 5 and input 2 got cost 48 , where there is 2 - 3 - 4 - 5 - 2 route with a cost 1 for Input 1 ( ( 3 2 0 ) , (3 4 0) , (5 4 0 ) , (2 5 1 ) )

and for input 2
{ (3 5 0) , (3 6 12), (6 9 11) ,(8 9 0), (5 8 0 ) } this will cost only 23

assuming a road (3 5 0) is same as ( 5 3 0 ) ,

"Every road connects two cities and can be traversed in both directions. "


please clear my doubt. and it would be better if you provide the least cost Path also , so we can understand how you got that value

Last edit: 2012-05-24 07:52:33

Added by:Stjepan Glavina
Date:2012-05-19
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOI 2007