attack-on-island-nation

This time Unseen gang has attack on "Island Nation". In Island Nation every city is located on an island, all the cities are connected by bridges (bidirectional). As per the plan of unseen gang, they have been successful in destroying all the bridges of the Island Nation connecting the cities. This has created terror among the peoples and government has decided to call Enigma Crew for help to maintain peace. Now, Enigma Crew has been assigned the task to construct bridges between cities, such that there exist a path between every city. As the distance between the cities vary, cost of building bridges also varies. As the economic times are not good enough, so Enigma Crew wants to minimise the total cost of construction. Now members of Enigma Crew has approached you for help in building the bridges such that cost is minimum. So given number of cities, number of bridges and cost of building that bridges, output the minimum cost for construction of bridges, such that there exist path between all the cities of Island Nation.

Input Format

First line of input contains two integers N and B, denoting number of cities and number of bridges connecting the cities respectively.
Next B lines contains, three integers a, b and c, where a and b are city names and c is the cost of bridge construction.

Output Format

Output the minimum cost of construction, fulfilling the condition that there a exist path from one city to every other cities of the Island Nation.

Constraints

1 ≤ N ≤ 100000  
1 ≤ B ≤ 100000 
1 ≤ c ≤ 100000  (cost of construction) 

SAMPLE INPUT
3 3
1 2 5
1 3 9
2 3 8

SAMPLE OUTPUT
13

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: