Frosted Footpaths

# Frosted Footpaths ## Problem Winter has arrived at MOOSACO Farm, and all the barns have become connected by frosted footpaths. Each footpath has been assigned a frost cost based on how treacherous it is to traverse. Farmer Bessie wants to ensure that all N barns can be reached from each other. She plans to clear footpaths one by one, starting with the least frosty (lowest frost cost) and working her way up. What is the minimum maximum frost cost that Bessie needs to clear in order to connect all N barns? In other words, if she processes the footpaths in order of increasing frost cost and stops as soon as all barns are connected, what is the highest frost cost of any footpath she had to clear? If it's impossible to connect all barns even after clearing all footpaths, output -1. ## Input The first line contains two integers N and M (1 ≤ N ≤ 10^5, 0 ≤ M ≤ 10^5), where: - N is the number of barns - M is the number of footpaths Each of the next M lines contains three integers u, v, and c (1 ≤ u, v ≤ N, 1 ≤ c ≤ 10^9), representing a footpath between barns u and v with frost cost c. ## Output Output the minimum maximum frost cost needed to connect all barns, or -1 if it's impossible. ## Constraints - 1 ≤ N ≤ 10^5 - 0 ≤ M ≤ 10^5 - 1 ≤ c ≤ 10^9 ## Sample Input ``` 4 5 1 2 5 2 3 4 3 4 7 1 4 20 2 4 8 ``` ## Sample Output ``` 7 ``` ## Explanation Bessie processes the footpaths in order of increasing frost cost: 1. Footpath (2, 3) with cost 4: Connect barns 2 and 3 2. Footpath (1, 2) with cost 5: Connect barn 1 to the group 3. Footpath (3, 4) with cost 7: Connect barn 4 to the group All barns are now connected using footpaths with maximum cost 7. Any footpath Bessie clears after this point is unnecessary.