熊猫先生正在沙漠中探险。他在沙漠中心的绿洲里发现了很多仙人掌。这片风景激发他想出了一个关于仙人掌的问题。

众所周知，仙人掌是一个连通的无向图，其中每条边最多属于一个简单环。给定一个加权图，其每个连通分量都是一个没有自环的仙人掌，你需要用给定的 $K$ 种颜色为每个顶点着色。要求每种颜色至少被使用一次。

熊猫先生想要最小化连接不同颜色顶点的边的权重之和。你能帮帮他吗？

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含三个整数 $N, M$ 和 $K$ ($1 \le N \le 10^5, 0 \le M \le 2 \times 10^5, 1 \le K \le \min\{N, 1000\}$)，其中 $N$ 是顶点数，$M$ 是边数，$K$ 是颜色数。我们保证所有测试用例中 $N$ 的总和不超过 $5 \times 10^5$。

接下来的 $M$ 行描述了顶点之间的边。每行包含 3 个整数 $x, y, w$ ($1 \le x \neq y \le N, 1 \le w \le 10^9$)，表示顶点 $x$ 和顶点 $y$ 之间存在一条权重为 $w$ 的边。

输出格式

对于每个测试用例，首先输出一行 “Case x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是连接不同颜色顶点的边的最小权重和。

然后输出一行包含 $N$ 个整数，第 $i$ 个整数表示第 $i$ 个顶点的颜色，任何合法的方案均可。请确保每种颜色至少被使用一次。

样例

输入 1

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

输出 1

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