Mở rộng mạng lưới cáp quang

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ thành phố. Hiện đã có sẵn $K$ tuyến cáp quang nối trực tiếp một số cặp thành phố (chi phí sử dụng là $0$). Ngoài ra, có $M$ tuyến cáp quang tiềm năng có thể xây dựng thêm, tuyến thứ $i$ nối $u_i, v_i$ với chi phí $w_i$. Hãy tìm tổng chi phí nhỏ nhất để xây dựng thêm cáp quang sao cho cả $N$ thành phố đều liên thông với nhau. Nếu không thể làm cho tất cả liên thông, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, K, M$ ($1 \le N \le 10^5$, $0 \le K, M \le 2 \cdot 10^5$).
  • $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ là một tuyến cáp đã có sẵn.
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $0 \le w \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là chi phí tối thiểu, hoặc -1.
Ví dụ
Input Output
4 1 3
1 2
2 3 5
3 4 2
1 3 10
7
4 1 1
1 2
3 4 5
-1
Giới hạn
  • $1 \le N \le 10^5$, $0 \le K, M \le 2 \cdot 10^5$
  • $0 \le w \le 10^9$
Draft saved