IITKESO207PA5Q3 - Road Network
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
Added by: | Programming Club, IITK |
Date: | 2018-03-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |