Minimum Cost to Connect Houses

You are given a village with \( n \) houses and \( m \) potential electrical lines connecting pairs of houses. Each electrical line is associated with a cost. Your task is to determine the minimum cost required to connect all houses. If it is impossible to connect all houses, output \( -1 \). This problem is a classic application of the Minimum Spanning Tree (MST) concept. The MST is defined by the formula:

\( MST = \min \sum_{e \in T} w(e) \)

where \( T \) is the set of edges included in the tree and \( w(e) \) is the cost of edge \( e \).

inputFormat

The first line contains two integers ( n ) and ( m ), where ( n ) is the number of houses and ( m ) is the number of possible electrical lines. Each of the following ( m ) lines contains three integers ( u ), ( v ), and ( w ), representing an electrical line connecting house ( u ) and house ( v ) with cost ( w ).

outputFormat

Output a single integer which is the minimum cost to connect all the houses. If it is impossible to connect all houses, output ( -1 ).## sample

4 5
1 2 1
1 3 4
2 3 2
2 4 3
3 4 5

6