33OJ
登录 注册

#P17808. [ICPC 2019 Nanchang R] Bob's Problem

[ICPC 2019 Nanchang R] Bob's Problem

Problem Description

Bob was in trouble. He rubbed the magic ring on his finger, and you came out of the ground.

You are given an undirected graph GG which contains nn vertices labelled from 11 to nn, with mm weighted edges between them coloured in black or white. You have to choose some edges in GG such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than kk white edges. There may be multiple available strategies to determine these edges, and you are asked to find out the way with a maximum total weight of edges.

Input Format

The first line contains an integer TT (1≤T≤51\leq T\leq 5) indicating the number of test cases.

For each test case, the first line contains three integers n (1≤n≤50000),mn~(1 \le n \le 50000), m and k (1≤k≤m≤500000)k~(1\le k\le m \le 500000).

Each of the following mm lines contains four integers u,v (1≤u,v≤n),w (0≤w≤100000)u, v~(1\le u,v\le n), w~(0\le w\le 100000) and c (0≤c≤1)c~(0\le c\le 1) describing an edge of weight ww and colour cc between the uu-th vertex and the vv-th vertex. Here an edge is white if c=1c = 1, or black if c=0c = 0.

Note that there may be multiple edges between some vertices, and self-loops are also allowed.

Output Format

For each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output -1 if there is no solution for the given graph.

1
5 6 2
1 2 0 0
1 3 5 1
1 5 1 0
2 3 6 1
2 4 2 0
3 4 7 1
16