### Woburn Challenge 2001

## Problem 8: Austin Powers III, Act I: Time to Get Medieval

The mind reader had no thoughts on the last Survivor. To salvage a bleak situation, M makes the following decision. As her last act as chief (before she is fired for losing the pool), she will mobilize a multinational commando unit from the Delta Force, GIGN, Mossad, SAS, and Task Force 2 and engage them in an operation quarterbacked by her 2nd best agent, Austin Powers. The force will perform a great service to humanity by removing Jerri from the list of applicants who applied to be on Survivor. Clearly, this requires time travel. However, time travel has changed somewhat and it turns out that only certain time periods can be reached. Moreover, only certain time conduits exist that allow travel between certain two time periods. The final problem is that the time machine needs to be hardwired with the subspace parameters of these conduits, with each conduit costing a different amount to hardwire. (Note that the conduits are bi-directional and that there may be multiple conduits connecting time periods, each costing different amounts).

Times are tough and you want to build the time machine of minimum cost, but still want to be able to reach all the time periods from any time period (possibly by stopovers at other time periods). If it isn’t possible to reach all time periods, then output `Requires more conduits`

.

### Input

The first line contains `T`, the number of test cases to follow.

The first line of each test case contains `N`, the number of time periods, (2 ≤ `N` ≤ 100) and `C`, the number of conduits (1 ≤ `C` ≤ 20000)

The remaining `C` lines of this test case each contain three integers `i`, `j`, `k` indicating that there is a conduit connecting time periods `i` and `j`, with a cost of `k` (`i` ≠ `j`, 1 ≤ `k` ≤ 200)

### Output

For each test case, output the minimum cost to connect all time periods, or `Requires more conduits`

if it is not possible to connect them all.

### Sample Input

`3`

5 5

1 2 1

2 3 2

3 4 3

4 5 4

5 1 5

6 9

1 5 6

1 6 2

2 3 7

2 5 1

1 2 9

3 5 4

2 6 3

2 4 4

1 3 6

4 4

1 2 82

2 3 1

1 2 12

3 1 31

### Sample Output

`10`

14

Requires more conduits

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Nov 23, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

jeffreyxiaoon Aug 07, 2014 - 1:57:24 am UTC Hint?Butaneon Aug 07, 2014 - 2:12:50 am UTC Re: Hint?jeffreyxiaoon Aug 07, 2014 - 2:20:20 am UTC Re: Hint?