#1339. TRICITY - Ba thành phố

Hệ thống giao thông của vương quốc Byteland gồm thành phố được kết nối bởi con đường hai chiều. Hệ thống đường này đảm bảo sự đi lại giữa hai thành phố bất kỳ.

Do nhu cầu phát triển kinh tế, nhà vua muốn nâng cấp hệ thống giao thông này bằng cách chuyển thành đường cao tốc. Vì kinh phí có hạn nên trước tiên nhà vua muốn chọn một số con đường để nâng cấp thành đường cao tốc sao cho thành phố trung tâm của vương quốc đi lại được với nhau chỉ bằng các đường cao tốc này.

Yêu cầu: Hãy giúp nhà vua chọn ra các con đường cần nâng cấp thành đường cao tốc sao cho tổng độ dài các con đường này là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương ;
• Dòng thứ hai chứa ba số nguyên khác nhau là số hiệu của ba thành phố trung tâm;
• dòng cuối, mỗi dòng chứa ba số nguyên thể hiện có một con đường hai chiều nối thành phố với thành phố có độ dài .

Dữ liệu ra:

• Một số nguyên duy nhất là tổng độ dài các con đườn cần nâng cấp thành đường cao tốc trong phương án tối ưu.

Ví dụ:

Dữ liệu vào:

5 6
1 3 5
1 2 10
1 5 1
5 2 1
1 4 1
4 3 3
3 2 2

Dữ liệu ra:

4