Wicked Lord Hyeyu
InterviewTime limit0.5sMemory limit512 MB
Build a minimum spanning tree over N villages with K weighted edges, then report the largest shortest-path distance between any two villages in that tree.
- Level
Medium6 of 10
- Topics
- Minimum spanning tree, Graph, DFS, Tree
- Solved
- No attempts yet
Problem
In the online game FT, Hyeyu became a lord through fierce competition and received a quest. The quest is to build trade routes between the villages she manages and boost exchange between them. Each trade route can be traveled in both directions, and the trade routes must be built so that no two villages are unreachable from each other.
Hyeyu, whose heart is spiteful, wants to complete the quest while spending as little money as possible. Help Hyeyu connect all the villages at minimum cost and find that cost. Hyeyu is also very interested in the worst possible travel cost between villages. Among the shortest paths between any two villages, find the cost of the path with the largest cost.
Input
The first line gives the number of villages N (1 ≤ N ≤ 1,000) and the number of trade routes that can be built K (1 ≤ K ≤ 1,000,000).
From the second line to the K + 1-th line, three values are given: the numbers a, b (a ≠ b) of two different villages and the cost c of connecting the two villages. (1 ≤ c ≤ 1,000,000)
The input is always given such that all villages can be connected, and the way to connect them at minimum cost is unique.
Between two different villages, at most one trade route can be built.
Villages are numbered from 0 to N - 1.
Output
On the first line, print the minimum cost of connecting all the villages.
On the second line, print the cost of the path with the largest travel cost between villages.