TopCoder

AA 競程
AA 競程是最強的!

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

50.0% (8/16)

Tags

Description

馬可(Mirko)和史拉可(Slavko)為了參加一年一度在克羅埃西亞(Coratia)舉行的雙人自行車馬拉松大賽正在加緊努力訓練。
他們須要選擇一條路線(route)來訓練。

在他們的國家有 N 座城市與 M 條雙向道路(roads)。每一條道路連接兩個城市。但只有 N-1條道路是已被鋪築好的,其它
的道路則是還沒被鋪築好的道路,幸好任兩座城市間都有一條用已鋪築好的道路路徑所連結。
換句話說,這 N 座城市與 N-1 條已被鋪築好的條道路形成了一顆樹狀結構

此外,每座城市最多可以是 10 條道路的端點

訓練的路線可以從某一座城市開始,在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點,所以他
們訂了一項規則: 就是絕不經過相同的城市絕不騎過相同的道路
訓練的路線可以在任何一座城市開始並且不須要經過每一座城市。

騎乘在後座是較輕鬆的,因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此,馬可和史拉可在每個城市會交換座位。
為了確保他們能獲夠得相同的訓練量,他們想要選擇一條含有偶數條道路的路線。

馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路,讓他們無法找到一條滿足上述條件的路線。
封鎖沒被鋪築好的道路須要付出一些代價(一個正整數) ,而已被鋪築好的道路是不可能被封鎖的。

寫一個程式,當給定城市與道路的描述後,找出封鎖道路使其無法滿足上述條件的訓練路徑之最小總代價。

Input Format

輸入的第一行有兩個整數 N 與 M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000),分別代表城市的數目與道路的數目。

接下來的 M 行每一行都有三個整數 A 、B 和 C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000),用來表示一條道路。
A 與 B 是不同的數字,表示直接由這條道路所連接的兩座城市。如果 C=0,表示該道路已被鋪築好了;
否則該道路是尚未被鋪築過,而 C 代表封鎖此一條道路所需付出的代價。

每座城市最多可以是 10 條道路的端點,且兩座城市間絕對不會有一條以上的道路直接連接。

Output Format

輸出一個整數,代表在上述問題描述中的最小總代價。

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

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

Hints

Problem Source

原TIOJ1346 / IOI 2007, Day 2 problemsetter: kelvin

Subtasks

No. Testdata Range Score
1 0 3
2 1 3
3 2 3
4 3 3
5 4 3
6 5 3
7 6 3
8 7 3
9 8 3
10 9 3
11 10 3
12 11 3
13 12 3
14 13 3
15 14 3
16 15 3
17 16 3
18 17 3
19 18 3
20 19 3
21 20 3
22 21 3
23 22 3
24 23 3
25 24 3
26 25 3
27 26 3
28 27 19

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 9000 65536 262144 1
1 9000 65536 262144 2
2 9000 65536 262144 3
3 9000 65536 262144 4
4 9000 65536 262144 5
5 9000 65536 262144 6
6 9000 65536 262144 7
7 9000 65536 262144 8
8 9000 65536 262144 9
9 9000 65536 262144 10
10 9000 65536 262144 11
11 9000 65536 262144 12
12 9000 65536 262144 13
13 9000 65536 262144 14
14 9000 65536 262144 15
15 9000 65536 262144 16
16 9000 65536 262144 17
17 9000 65536 262144 18
18 9000 65536 262144 19
19 9000 65536 262144 20
20 9000 65536 262144 21
21 9000 65536 262144 22
22 9000 65536 262144 23
23 9000 65536 262144 24
24 9000 65536 262144 25
25 9000 65536 262144 26
26 9000 65536 262144 27
27 9000 65536 262144 28