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.|

LQDXEUI - 2 xe ủi

Một thành phố gồm n địa điểm và n-1 con đường nối chúng .Từ mỗi địa điểm có thể đi đến các địa điểm còn lại qua đúng 1 tuyến đường.
Mùa đông,các con đường bị phủ bởi lớp tuyết rất dày nên giao thông bị tắc nghẽn.Ngài thị trưởng thành phố đã cho 2 xe ủi để ủi tuyết.
Ban đầu 2 xe đứng ở địa điểm X. Chi phí di chuyển trên con đường đúng bằng độ dài con đường đó . Một con đường được ủi nếu có ít nhất con xe di chuyển qua con đường đó .Hai xe sẽ dừng lại nếu tất cả các con đường đã được ủi.
Yều cầu : Tìm cách ủi sao cho tổng chi phí nhỏ nhất

Input

Dòng đầu chứa số nguyên N và X (N<=105)
N-1 tiếp theo, mỗi dòng chứa ba số nguyên u, v và t có nghĩa có tuyến đường nối 2 địa điểm u và v với chi phí t (t<=103)


Output

Xuất ra tổng chi phí nhỏ nhất

Example

Input: 

4 1
1 3 2
1 2 3
1 4 4


Output:

11
Input: 

6 1
1 2 1
2 3 1
1 4 1
4 5 1000
4 6 1000


Output:

2006
Ở ví dụ 1 : xe 1 di chuyển sang địa điểm 3 rồi sang lại địa điểm 1
                  (chi phí = 2+2).
Sau đó xe 1 sang địa điểm 2 ,xe 2 sang địa điểm 4 (chi phí =3+4)
Tổng chi phí là 2+2+3+4=11
Ở ví dụ 2 : xe 1 di chuyển sang địa điểm 2 rồi sang địa điểm 3,
sau đó sang lại địa điểm 2 rồi sang lại địa điểm 1.(chi phí = 1+1+1+1)
Sau đó 2 xe cùng di chuyển sang địa điểm 4 (chi phí = 1+1)
Rồi xe 1 di chuyển sang địa điểm 5 và xe 2 di chuyển
     sang địa điểm 6 (chi phí = 1000+1000)
Tổng chi phí = 1+1+1+1+1+1+1000+1000=2006


 

Được gửi lên bởi:Trung Hieu
Ngày:2009-07-19
Thời gian chạy:0.129s
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 PERL6 PYPY RUST SED VB.NET

hide comments
2017-12-28 17:06:47
ledacthuongvq
2016-12-30 02:18:28
TÌm 2 đường đi dài nhất không giao nhau :)
2013-11-26 04:34:53 a;slkfjasl;fkj
cũng khoai đấy ta :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.