题目描述
Problem Description
Mirko and Slavko are紧张训练 for the annual two-person cycling marathon in Croatia. They need to choose a training path.
Their country has \( N \) cities and \( M \) roads. Each road connects two cities. Among these roads, exactly \( N-1 \) are paved, and the rest are unpaved dirt roads. Fortunately, there exists a path composed of paved roads between any two cities. In other words, these \( N \) cities and \( N-1 \) paved roads form a tree structure.
Additionally, each city is the endpoint of at most \( 10 \) roads.
A training path starts in a city, traverses some roads, and ends in the same starting city. Since Mirko and Slavko like to visit new cities, they have set a rule: they will never pass through a city they have already visited, and they will never ride on the same road twice (regardless of direction). The training path can start in any city and does not need to visit all cities.
Obviously, the rider in the back seat has an easier time, as the front rider can shield them from the wind. For this reason, Mirko and Slavko switch positions in each city. To ensure their training intensity is equal, they need to choose a path with an even number of roads.
Mirko and Slavko's competitors have decided to set up obstacles on some of the unpaved dirt roads to prevent them from finding a training path that meets the above requirements. It is known that setting up an obstacle on each dirt road has a cost (a positive integer), and competitors cannot set up obstacles on paved roads.
Given the description of the city and road network, write a program to calculate the minimum total cost required to ensure that no training path meeting the above requirements exists.
Input Format
The first line of input contains two integers \( N \) and \( M \) (\( 2 \leq N \leq 1000 \), \( N-1 \leq M \leq 5000 \)), representing the number of cities and roads, respectively. The next \( M \) lines each contain three integers \( A \), \( B \), and \( C \) (\( 1 \leq A \leq N \), \( 1 \leq B \leq N \), \( 0 \leq C \leq 10000 \)), describing a road. \( A \) and \( B \) are different integers representing the two cities connected by this road. For paved roads, \( C \) is \( 0 \); for dirt roads, \( C \) is the cost required to set up an obstacle on that road. Each city is the endpoint of at most \( 10 \) roads. No two cities will have more than one direct road connecting them.
Output Format
The output should contain a single integer, representing the minimum total cost calculated.
Sample Input and Output
Input Sample #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
Output Sample #1
5
Input Sample #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
Output Sample #2
48
Notes/Hints
The first sample's road and city layout. Paved roads are shown with thick lines.
There are 5 possible routes. If edges 1-3, 3-5, and 2-5 are blocked, the two will not be able to use any of the 5 routes. The cost of blocking these three edges is 5.
Blocking only two edges, such as 2-4 and 2-5, is also possible, but this would result in a higher cost, 6.
In the first 30 points of test data, the paved roads will form a chain.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分