Nitish is the Minister of Road Transport and Highways in the country of Byteland. As a part of his duty, he has been assigned a job to design the highway network connecting various cities. All highways support two-way traffic. Some pairs of cities can have highways between them, while others cannot. Moreover, Nitish also knows the exact cost of constructing the highway between two cities, if it can be constructed. However, the condition is that the network should allow someone to reach from one city to another, possibly by a sequence of highways. In other words, on the completion of the road network, there should not exist cities a, b such that there is no way to go from a to b via the highway network.

Nitish has heard of your algorithmic skills and has enlisted your help. You are required to tell him the minimum cost which he must incur to construct the network provided that the condition is satisfied.

Input

The first line of input consists of 2 space separated integers n and m. n represents the total number of cities in the country. m lines follow.

Each of the m lines contains 3 space separated integers x y c, denoting that a highway can be built between x and y with cost c. (0 <= x, y <= n-1)

Output

Output a single number indicating the total cost of the highway network.

Constraints

Constructing a road has a positive integral cost. (c > 0).

Example

Input:
5 5
0 1 10
2 3 2
0 2 10
1 4 10
0 4 1

Output:
23