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

NỐI MẠNG

Có N thành phố và M tuyến đường dự kiến có thể xây dựng để kết nối chúng. Mỗi tuyến
đường nối hai thành phố u,v với chi phí xây dựng W.

Yêu cầu: Hãy chọn ra các tuyến đường sao cho tất cả các thành phố đều có thể đi đến nhau và
tổng chi phí xây dựng là nhỏ nhất.

Dữ liệu vào

o Dòng 1: Hai số nguyên N,M (1≤N≤105,1≤M≤2x105).
o M dòng tiếp theo: Mỗi dòng gồm 3 số u,v,W (1≤u,v≤N,W≤109).

Kết quả: Tổng chi phí nhỏ nhất. Nếu không thể kết nối toàn bộ, in IMPOSSIBLE.

Ví dụ

INPUT                                 OUTPUT                               GIẢI THÍCH
 5 6                                   15                                   Có 5 thành phố và 6 tuyến
                                                                            đường có thể xây dựng. Để
 1 2 3                                                                      tối ưu chi phí, chúng ta sẽ
                                                                            chọn xây dựng 4 tuyến
 1 3 4                                                                      đường sau:
 2 3 5                                                                               Tuyến (2, 4) với chi
                                                                                      phí 2.
                                                                                     Tuyến (1, 2) với chi
 2 4 2                                                                                phí 3.
                                                                                     Tuyến (1, 3) với chi
 3 5 7                                                                                phí 4.
                                                                                     Tuyến (4, 5) với chi
 4 5 6                                                                                phí 6.

                                                                            Lúc này, cả 5 thành phố đều
                                                                            đã được kết nối với nhau (1
                                                                            nối với 3 và 2; 2 nối với 4; 4
                                                                            nối với 5). Tổng chi phí xây
                                                                            dựng là: 2 + 3 + 4 + 6 = 15.
                                                                            Tuyến (2, 3) và (3, 5) bị bỏ
                                                                            qua để tiết kiệm chi phí vì
                                                                            các thành phố này đã có thể
                                                                            đi đến nhau qua các tuyến
                                                                            đường khác.