# DCP-344: Repairing Road Back to All Problems

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

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 1.00 C++14 2.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 54/132

Solve/Submission

### Ranking

# User Language Timing
01 Morass Cpp14 0.04s
02 tasnidmahin Cpp 0.06s
03 Zeronfinity Cpp14 0.06s
04 I_See_You Cpp14 0.06s
05 tariqiitju Cpp14 0.06s
06 sazal_dev Cpp 0.06s
07 mno123 Cpp 0.06s
08 Brokenlog Cpp14 0.07s
09 Aman_khan Cpp 0.07s
10 Jisancse Cpp14 0.07s
11 ksohan Cpp 0.07s
12 as_couple Cpp14 0.07s
13 nafiz0080 Cpp14 0.07s
14 nayan32biswas Cpp14 0.07s
15 feodorv C 0.07s
16 SakibAlamin Cpp14 0.08s
17 Double_O Cpp14 0.08s
18 njrafi Cpp 0.08s
19 shaft Cpp 0.08s
20 ssavi Cpp14 0.08s
21 Ishrak Cpp 0.08s
22 prodipdatta7 Cpp14 0.08s
23 pulak_ict_mbstu Cpp14 0.08s
24 prateepm Cpp14 0.09s
25 Mahmudul_Tushar Cpp 0.10s
26 dmehrab06 Cpp 0.11s
27 alttlprgrmmng Cpp 0.13s
28 mahbubcseju Cpp14 0.13s
29 Masum_ice Cpp14 0.13s
30 AlaminJust Cpp14 0.13s
31 swapnil Cpp14 0.14s
32 Faizul_BU Cpp 0.16s
33 moshiur_cse15 Cpp14 0.17s
34 FariD Cpp14 0.18s
35 hrOarr Cpp14 0.18s
36 jamil993 Cpp14 0.20s