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

QBBUILD - Xây dựng đường

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbbuild


Vua Peaceful vừa khai hoang một vùng đất để lập ra đất nước Peace, lúc đầu chỉ có N thành phố (được đánh số từ 1 đến N) và không có con đường nào.

Vua Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế nhà vua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4 thành phố đặc biệt đó vẫn liên thông.

Bạn được biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn một số con đường để xây dựng để theo đúng ý nhà vua biết rằng luôn tồn tại ít nhất một phương án xây dựng đường sao cho 4 thành phố đặc biệt liên thông.

Input

Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố.( 1 ≤ N ≤ 100 )

Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt.

Trong một số dòng tiếp theo, mỗi dòng ghi 3 số nguyên u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp giữa 2 thành phố u và v thì chi phí là c. ( 1 ≤ c ≤ 5000 )

Output

Gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ thống đường.

Example

Input:
5
2 3 4 1
1 2 10
1 5 1
5 2 1
1 4 1
4 3 3
3 2 2

Output:
5

Được gửi lên bởi:special_one
Ngày:2008-12-10
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 PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOICAMP 3

hide comments
2021-05-27 18:03:46
Tham khảo: https://vnspoj.github.io/problems/QBBUILD
2019-10-20 16:50:58
kham khảo lời giải:
https://vietcodes.github.io/code/150/index.html
2017-07-24 05:09:46
2 đấm vẫn không AC :(
2016-12-19 21:31:20
đm nộp nhầm c++11 thành c++
2016-11-24 09:22:49
DP BITMASK, max dị haha
2016-10-08 19:21:51
thank nong dan john v.v
2015-11-03 04:43:42 _sanghk11_
nếu N < 4 thì dòng 2 ghi 4 số nào ??????
2015-09-10 17:02:44
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/10/xay-dung-duong-qbbuild/

Last edit: 2015-10-02 03:32:06
2015-08-01 17:19:03 N�ng D�n John
http://ideone.com/HxhrpE
2015-07-30 15:21:35 N�ng D�n John
NGAY PHÁT ĐẦU ĐÃ AC =)) ĐỜI THẬT ĐẸP
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.