## Cable TV

You would like to provide citizens of a newly constructed neighborhood with cable television.As a computer scientist, you know this calls for... wires!

Surveyors have done their work and have given you the cost of connecting pairs of locations.

However, they have also warned you that certain links might be dangerous - there is a risk of interference from power lines and such.

Find the minimum cost to connect all the houses, minimizing the cost but above all minimzing the number of dangerous links used.

### Input

N ≤ 100, the number of locations.M ≤ 10000, the number of possible links.

M lines, each with four integers a,b,c,d.

Each line signifies a possible (bidirectonal) link between locations a and b, with cost c.

*d*will be 1 if the link is dangerous, and 0 otherwise.

### Output

Two integers.Output a) the minimum number of dangerous links required and b) the total minimum cost.

### Sample Input

4 4 1 2 2 0 2 3 1 1 3 1 1 0 3 4 1 1

### Sample Output

1 4

Take 1-2, 3-1, and 3-4.

The use of one dangerous cable is inevitable, but we can avoid the use of the other.

All Submissions

Best Solutions

**Point Value:** 15

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Mar 04, 2009

**Problem Types:**[Show]

**Languages Allowed:**

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

## Comments (Search)

jimgaoon Feb 16, 2015 - 3:16:31 am UTC Both dangerous and non-dangerous cost on the same edge?1 2 10 0

1 2 20 1

It was not stated in the problem.

jargonon Feb 16, 2015 - 7:04:24 pm UTC Re: Both dangerous and non-dangerous cost on the same edge?That said, a well-written solution should not care that there are multiple possible links.

jimgaoon Feb 16, 2015 - 9:14:51 pm UTC Re: Both dangerous and non-dangerous cost on the same edge?xiaowuc1on Jun 19, 2014 - 3:32:35 am UTC No stated bounds on costBon Sep 22, 2013 - 9:32:06 pm UTC Are the two integers for the same case?Alexon Sep 22, 2013 - 9:49:07 pm UTC Re: Are the two integers for the same case?