Nối lại nhịp cầu

Buổi 24 — Mock Contest Phase 1
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Quần đảo gồm $N$ hòn đảo đánh số từ $1$ đến $N$. Hiện tại đã có $M$ cây cầu miễn phí nối một số cặp đảo. Bạn có danh sách $K$ dự án xây cầu mới, dự án thứ $i$ nối hai đảo $u_i$ và $v_i$ với chi phí $w_i$.

Hãy chọn một số dự án để xây dựng sao cho tất cả $N$ hòn đảo đều liên thông với nhau (có thể đi lại giữa hai đảo bất kỳ) với tổng chi phí nhỏ nhất. Nếu không thể làm cho tất cả các đảo liên thông, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, M, K$ ($1 \le N \le 10^5$, $0 \le M, K \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) là các cây cầu có sẵn.
  • $K$ dòng cuối cùng, 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$) là các dự án cầu mới.
Dữ liệu ra
  • Một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc -1 nếu không thể.
Ví dụ
Input Output
4 2 3
1 2
3 4
1 3 5
2 4 3
1 4 10
3
4 1 1
1 2
3 4 5
-1
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M, K \le 2 \cdot 10^5$.
  • $1 \le w_i \le 10^9$.
Draft saved