Hội thảo bằng điện thoại

Một công ty điện thoại cần tổ chức một cuộc hội thảo cho 3 khách hàng trên đường trường thông. Dịch vụ cần đảm bảo cho 3 khách hàng có thể trao đổi với nhau đồng thời. Mỗi khách hàng có thể thâm nhập vào mạng truyền thông qua các cổng thâm nhập. mạng truyền thông bao gồm các cổng thâm nhập được nối với nhau bằng các kênh  điện thoại hai chiều. Ba khách hàng cần thâm nhập vào mạng từ 3 cổng khác nhau sao cho tổng chi phí để liên kết họ là ít nhất. Chú ý là được phép liên kết hai cổng thâm nhập bất kỳ. Bạn được biết các kênh nối giữa các cổng cùng với chi phí liên kết chúng. Bạn cần tìm liên kết đòi hỏi chi phí ít nhất để nối 3 cổng thâm nhập của 3 khách hàng tham gia hội thảo. Các cổng được đánh số từ 1 đến N.

Dữ liệu vào: từ file văn bản CONF.INP

+ Dòng đầu tiên chứa hai số nguyên N và E, trong đó N≤100 là số cổng, E là số kênh giữa các cổng

+ Mỗi dòng thứ K trong số E dòng tiếp theo chứa 3 số nguyên i, j, c_ij cho biết kênh nối thứ k nối hai cổng i với j và chi phí để liên kết hai cổng này là c_ịj (1≤c_ij≤100)

+ Dòng cuối cùng chứa 3 số nguyên là chỉ số của 3 cổng mà từ đó 3 khách hàng tham gia hội thảo thâm nhập vào mạng

Dữ liệu ra: ghi vào file CONF.OUT

+ Dòng đầu tiên chứa S là tổng chi phí theo cách liên kết tìm được và R là số kênh nối cần sử dụng

+ Một trong các dòng tiếp theo chứa 2 số của hai đầu mút của kênh cần sử dụng trong cách liên kết đó.

CONF.INP	CONF.OUT
8 12 1 2 20 2 3 8 2 4 3 2 5 3 2 6 6 3 5 2 3 6 9 4 7 5 5 6 1 5 7 7 6 8 4 7 8 6 1 4 6	27 4 1 2 2 4 2 5 5 6

 

SOLUTION - TEST