Elearning CodePath – CTP Online Judge

Mạng điện tiết kiệm

DSU05_MST

## Đề bài

Có `N` trạm điện được đánh số từ `1` đến `N` và `M` đường dây có thể xây. Đường dây thứ `i` nối hai trạm `u_i`, `v_i` và có chi phí `w_i`.

Hãy chọn một số đường dây sao cho:

- Tất cả `N` trạm điện được kết nối với nhau.
- Tổng chi phí là nhỏ nhất.

Nếu không thể kết nối tất cả các trạm, in `-1`.

## Dữ liệu vào

- Dòng đầu gồm hai số nguyên `N M`.
- `M` dòng tiếp theo, mỗi dòng gồm `u_i v_i w_i`.

## Dữ liệu ra

In ra tổng chi phí nhỏ nhất để kết nối tất cả các trạm, hoặc `-1` nếu không thể.

## Ràng buộc

- `1 <= N <= 200000`
- `0 <= M <= 300000`
- `1 <= u_i, v_i <= N`
- `u_i != v_i`
- `-10^9 <= w_i <= 10^9`
- Có thể có nhiều đường dây nối cùng một cặp trạm.

## Subtask

| Subtask | Điểm | Ràng buộc |
| --- | ---: | --- |
| 1 | 20 | `N <= 8`, `M <= 28` |
| 2 | 30 | `N <= 2000`, `M <= 5000` |
| 3 | 50 | Không có ràng buộc bổ sung |

## Ví dụ

### Input

```text
4 5
1 2 3
2 3 4
1 3 10
3 4 2
2 4 8
```

### Output

```text
9
```

## Giải thích ví dụ

Chọn các đường dây:

- `3 - 4` chi phí `2`
- `1 - 2` chi phí `3`
- `2 - 3` chi phí `4`

Tổng chi phí là `9`, và tất cả trạm được kết nối.

✅ Đã AC: 2 / 2 submissions