Mô tả và yêu cầu

Trung tâm dịch vụ
Có N địa điểm dân cư đánh số từ 1 đến N. Giữa M cặp địa điểm trong số N địa điểm nói
trên có tuyến đường nối chúng. Người ta cần đặt một trung tâm dịch vụ tổng hợp tại một
địa điểm trùng với một địa điểm dân cư sao cho tổng khoảng cách từ trung tâm dịch vụ đến
N - 1 địa điểm dân cư còn lại là nhỏ nhất. Ta gọi khoảng cách giữa hai địa điểm là độ dài
đường đi ngắn nhất nối chúng. Giả sử N địa điểm trên là liên thông với nhau. Nếu có nhiều
phương án thì đưa ra phương án đặt trung tâm dịch vụ tại địa điểm có số hiệu nhỏ nhất.
Yêu cầu: Tìm địa điểm dân cư để đặt trung tâm dịch vụ mà tổng khoảng cách từ trung tâm
dịch vụ đến các địa điểm dân cư khác là nhỏ nhất.
Dữ liệu: Vào từ file văn bản TTDV.INP gồm M + 1 dòng:
 Dòng thứ nhất chứa hai số nguyên dương N và M.
 M dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương x, y, z, ở đó hai số đầu x, y là
số hiệu của hai địa điểm dân cư được nối với nhau bởi một tuyến đường, còn số thứ
ba z là độ dài của tuyến đường này.
Kết quả: Ghi ra file văn bản TTDV.OUT gồm 2 dòng:
 Dòng thứ nhất ghi địa điểm đặt trung tâm dịch vụ.
 Dòng thứ hai ghi tổng khoảng cách từ trung tâm dịch vụ đến các địa điểm dân cư
khác.

Ví dụ

TTDV.INP               TTDV.OUT
                                5 7                    3
                                1 2 9                  15
                                2 3 4
                                1 4 2
                                4 5 5
                                5 3 1
                                5 1 5
                                3 1 4
Ràng buộc:
        1  N  500; 1  M  250000; 1  z  105.