Cây khung nhỏ thứ hai

Buổi 20 — Cây khung nhỏ nhất
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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$
Draft saved