Cây khung nhỏ thứ hai
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh. Cây khung nhỏ thứ hai (Strictly Second Minimum Spanning Tree) là cây khung có tổng trọng số lớn hơn hẳn tổng trọng số của cây khung nhỏ nhất, nhưng nhỏ nhất trong tất cả các cây khung như vậy.
Hãy tìm tổng trọng số của cây khung nhỏ thứ hai, hoặc in ra -1 nếu đồ thị không liên thông hoặc không tồn tại cây khung nào có tổng trọng số lớn hơn hẳn cây khung nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là trọng số cây khung nhỏ thứ hai, hoặc
-1nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 1 2 3 2 3 4 3 1 4 4 2 4 5 |
7 |
| 3 3 1 2 1 2 3 1 1 3 1 |
-1 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le w_i \le 10^9$
Community Discussion