COMPANYS - Two Famous Companies

### 题目描述 给你一个带权无向图， 每条边非白即黑， 现要构造一个生成树使得恰有K条白色的边，使权值和最小 ### 输入 本题为多组数据，对于每组数据： 第一行依次输入点数n,边数m,需要的白色边数K； 此后m行依次输入a,b,c,x; 分别代表这条边所连接的两点，这条边的长度，这条边的颜色（0表示白色，1表示黑色） ### 输出 对于每组数据 输出一行“Case i ans”; i表示组数，ans表示本组所求的最小权值和 ### 数据范围 1<=n<=50,000; 1<=m<=100,000; 1<=a,b<=n-1; x=0,1;

In China, there are two companies which offer the internet service for the people from all cities: China Telecom and China Unicom. They both are planning to build cables between cities. The government wants to connect all the cities in minimum costs of course. So the minister of finance Mr. B wants to choose some of the cable plans from the two companies and calculate the minimum cost needed to connect all the cities. Mr. B knows that there are **N**-1 cables should be built in order to connect all **N** cities of China. For some political reason, Mr. B should choose **K** cables from the China Telecom and the rest **N**-1-**K** cables from the China Unicom. Your job is to help Mr. B determine which cables should be built and the minimum cost to build them. You may assume that the solution always exists.

Each test case starts with a line containing the number of cities **N** (1 <= **N** <= 50,000), number of cable plans **M** (**N**-1 <= **M** <= 100,000) and the number of required cables from China Telecom **K** (0 <= **K** <= **N**-1). This is followed by **M** lines, each containing four integers **a**, **b**, **c**, **x** (0 <= **a**, **b** <= N-1, **a** != **b**, 1 <= **c** <= 100, **x**=\[0,1\]) indicating the pair of cities this cable will connect, the cost to build this cable and the company this cable plan belongs to. **x**=0 denotes this cable plan belongs to China Telecom and **x**=1 denotes this cable plan is from China Unicom.

For each test case, display the case number and the minimum cost of the cable building plan.

2 2 1
0 1 1 1
0 1 2 0
2 2 0
0 1 1 1
0 1 2 0

Case 1: 2
Case 2: 1