Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRAINING - IOI07 Training

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274834/problem/T

Mirko và Slavko đang luyện tập vất vả cho kỳ thi xe đạp đôi hàng năm ở Croatia. Họ cần lựa một lộ trình để luyện tập.

Có N thành phố và M con đường hai chiều trên đất nước. Có đúng N-1 con đường được trải nhựa. Thật may là luôn có cách di chuyển giữa hai thành phố bất kỳ mà chỉ đi qua các con đường trải nhựa.

Thêm vào đó, có nhiều nhất là 10 con đường nối với mỗi thành phố.

Một lộ trình luyện tập bắt đầu từ một thành phố, đi theo một số con đường và trở về thành phố ban đầu. Mirko và Slavko muốn thăm thú các địa điểm mới, do đó họ sẽ không bao giờ đi qua một thành phố hoặc theo một con đường hai lần.

Lộ trình luyện tập có thể bắt đầu từ bất kỳ thành phố nào và không nhất thiết phải thăm tất cả các thành phố.

Đạp xe ở yên sau dễ hơn vì người đạp được che gió bởi người ngồi trước. Do đó, Mirko và Slavko đổi chỗ ở mỗi thành phố. Để đảm bảo cùng thời lượng luyện tập, họ sẽ chọn một lộ trình với số đường là số chẵn.

Các đối thủ của Mirko và Slavko quyết định chặn một số con đường không được trải nhựa để họ không thể tìm một lộ trình thỏa mãn các yêu cầu trên. Mỗi con đường không trải nhựa tốn một chi phí để chặn con đường đó.

Yêu cầu

Viết chương trình nhập mạng lưới thành phố và các con đường, tìm tổng chi phí nhỏ nhất để chặn các con đường sao cho không tồn tại lộ trình luyện tập nào thỏa mãn các ràng buộc nêu trên.

Dữ liệu

Dòng đầu tiên chứa hai số N và M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000), số thành phố và số con đường.

Mỗi trong số M dòng tiếp theo chứa 3 số nguyên A, B, C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000) mô tả một con đường. A, B là hai số phân biệt mô tả chỉ số của hai thành phố ở hai đầu con đường. Nếu C = 0, con đường được trải nhựa; nếu không, con đường không được trải nhựa và C là chi phí để chặn con đường. Mỗi thành phố nối với nhiều nhất 10 con đường. Không bao giờ có nhiều hơn một con đường nối trực tiếp giữa hai thành phố.

Kết quả

Trả về một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Ví dụ

Dữ liệu
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

Kết quả
5

Dữ liệu
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

Kết quả
48

Hình vẽ trên mô tả mạng lưới đường và thành phố trong ví dụ 1. Các đường trải nhựa được tô đậm. Có 5 lộ trình Mirkov và Slavko có thể chọn. Nếu các con đường 1-3, 3-5 và 2-5 bị chặn, Mirko và Slavko sẽ không dùng được 5 lộ trình này. Tổng chi phí để chặn các con đường này là 5.

Ta cũng có thể chỉ chặn 2 con đường, 2-4 và 2-5, tuy nhiên làm như vậy sẽ mất tổng chi phí cao hơn là 6.


Được gửi lên bởi:Jimmy
Ngày:2008-12-13
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:IOI 2007 - Croatia

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.