Cấp nước cho các làng

Có $n$ ngôi làng đánh số từ $1$ đến $n$, hiện chưa làng nào có nước sạch. Để cấp nước cho làng $i$, có thể khoan một giếng ngay tại làng với chi phí $c_i$. Ngoài ra có $m$ phương án đặt ống nước, phương án thứ $j$ đặt một đường ống nối làng $u_j$ với làng $v_j$ với chi phí $w_j$; nước chảy được theo cả hai chiều của ống.

Một làng có nước sạch nếu tại làng đó có giếng, hoặc từ làng đó đi theo các đường ống đã đặt (có thể qua nhiều làng khác) tới được một làng có giếng. Hãy tìm tổng chi phí nhỏ nhất để mọi làng đều có nước sạch.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa ba số nguyên $u_j,v_j,w_j$ ($u_j\ne v_j$).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le 5·{10}^4$
• $0\le m\le {10}^5$
• $1\le c_i,w_j\le {10}^9$
• $1\le u_j,v_j\le n$, $u_j\ne v_j$

Ví dụ