Medium Graph Theory > Minimum Spanning Tree

In middle east there is famous country having **N** towns. Every people in every towns wants to visit other people in different towns as they want to form friendship among everyone. But due to a sudden disaster, the roads between each town got destroyed. Also there are **M** companies who have some machine to construct a road. Each company machines have a fitness value **C** and each company propose to construct a road between town **A** and town **B**. Now **Mr. Shakil** is the chief engineer of constructing some roads for the country, and he wants to select minimum company such that any town people can go any town and total fitness of the machine should be maximized. He is in a dilemma how to select such companies. So he asked for your help. Input: ------ First line of input is a number **T (1 <= T <= 10)**. Each case starts with a line containing an integer **n (2 <= n <= 100000)** denoting number of towns and **m (n <= m <= 100000)** donating the number of company. Next m line contain three integer **u (1 <= u <= n), v (1 <= u <= n, v != u)** and **f((1 <= f <= 100000000)),** that’s mean ith **(1 <= i <= m)** company wants to construct a road between town **u** and **v** and fitness value of their machine is **f**. You can assume that ans is always possible. Output: ------- For each case of input, print the case number as **"Case #: x y"**, # is replaced by the case number starting from 1 and x is replaced by the minimum number of company need and y replaced by the maximum fitness value can make by the minimum number of company. Sample Input ------------ 1 3 3 1 2 1 2 3 2 3 1 3 Sample Output ------------- Case 1: 2 5

MD Musfiqur Rahman Sanim