# 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

# 56/163

Solve/Submission

### Ranking

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