405718: GYM102055 E Mr. Panda and Cactus

Mr. Panda is exploring in a desert. He finds that there are many cactuses growing in the oasis in the center of the desert. The scenery inspires him to come up with a cactus problem.

As we know, a cactus is a connected undirected graph with each edge belonging to at most one simple cycle. Given a weighted graph with each connected component being a cactus with no self loops, you are requested to color each vertex with one of the given $$$K$$$ colors. Each color is required to be used at least once.

Mr. Panda wants to minimize the sum of weight of edges which connects vertices of different color. Could you help him?

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 100$$$). $$$T$$$ test cases follow.

For each test case, the first line contains three integers $$$N$$$, $$$M$$$ and $$$K$$$ ($$$1 \le N \le 10^{5}$$$, $$$0 \le M \le 2 \times 10^{5}$$$, $$$1 \le K \le \min\{N, 1000\}$$$), where $$$N$$$ is the number of vertices, $$$M$$$ is the number of edges, and $$$K$$$ is the number of colors. We ensure the sum of $$$N$$$ in all cases is not greater than $$$5 \times 10^{5}$$$.

The following $$$M$$$ lines describe the edges between the vertices. Each line contains 3 integers $$$x, y, w$$$ ($$$1 \le x \neq y \le N$$$, $$$1 \le w \le 10^{9}$$$), representing an edge with weight $$$w$$$ between vertex $$$x$$$ and vertex $$$y$$$.

For each test case, output one line containing "Case x: y" first, where x is the test case number (starting from $$$1$$$) and y is the minimum sum of weight of edges which connects vertices of different color.

Then output a line consists of $$$N$$$ integers, the $$$i^{th}$$$ integer is the color of $$$i^{th}$$$ vertex, any valid way is acceptable. Make sure each color is used at least once.

3
4 3 2
1 2 5
2 3 4
2 4 7
3 3 3
1 2 100
2 3 10
3 1 4
4 5 3
2 3 7
3 4 3
4 2 5
1 3 6
3 1 5

Case 1: 4
1 1 2 1
Case 2: 114
1 2 3
Case 3: 15
1 2 1 3