{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBob was in trouble.He rubbed the magic ring on his finger, and you came out of the ground.\u003c/p\u003e\n\u003cp\u003eYou are given an undirected graph $G$ which contains $n$ vertices labelled from $1$ to $n$, with $m$ weighted edges between them coloured in black or white.You have to choose some edges in $G$ such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than $k$ 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.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line contains an integer $T$ ($1\\leq T\\leq 5)$ indicating the number of test cases.\u003c/p\u003e\n\u003cp\u003eFor each test case, the first line contains three integers $n~(1 \\le n \\le 50000), m$ and $k~(1\\le k\\le m \\le 500000)$.\u003c/p\u003e\n\u003cp\u003eEach of the following $m$ lines contains four integers $u, v~(1\\le u,v\\le n), w~(0\\le w\\le 100000)$ and $c~(0\\le c\\le 1)$ describing an edge of weight $w$ and colour $c$ between the $u$-th vertex and the $v$-th vertex. Here an edge is white if $c \u003d 1$, or black if $c \u003d 0$.\u003c/p\u003e\n\u003cp\u003eNote that there may be multiple edges between some vertices, and self-loops are also allowed.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output \u003ccode\u003e-1\u003c/code\u003e if there is no solution for the given graph.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n5 6 2\n1 2 0 0\n1 3 5 1\n1 5 1 0\n2 3 6 1\n2 4 2 0\n3 4 7 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}