Xây dựng mạng lưới đường

Một tỉnh có $n$ thành phố đánh số từ $1$ đến $n$, hiện chưa có con đường nào. Có $m$ phương án xây đường, phương án thứ $i$ xây một con đường hai chiều nối thành phố $u_i$ với thành phố $v_i$ với chi phí $w_i$.

Hãy chọn một số phương án để xây sao cho từ mỗi thành phố đều đi được tới mọi thành phố khác (có thể đi qua các thành phố trung gian), và tổng chi phí là nhỏ nhất.

Lưu ý: có thể có nhiều phương án nối cùng một cặp thành phố, và có phương án với $u_i=v_i$ (con đường đó vô dụng).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất. Nếu không thể nối tất cả các thành phố, in ra $-1$.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le m\le 2·{10}^5$
• $1\le u_i,v_i\le n$
• $1\le w_i\le {10}^9$

Ví dụ