图像分割

图像分割实际上是图的连通分量划分问题。将每个像素看成图中的一个顶点，顶点之间的边有权重，是相邻两个像素之间的区分度（非负整数）。图像分割的目标就是将图像构成的图分割成若干个不相交的连通分量，使得同一个分量中的像素都相似，而不同分量中的像素不相似。

连通分量的定义如下：

• 连通分量是一个互相连通的顶点的集合；

• 任何两个连通分量之间没有共同的顶点；

• 任何两个连通分量 C1 和 C2 之间的区分度 D(C1, C2) 大于这两个连通分量的内聚度 H；

• 区分度 D(C1, C2) 定义为连接 C1 和 C2 的所有边权重中的最小值，如果不存在连接边，则这个值定义为无穷大；

• 连通分量 C 的内聚度 H(C) 定义为 C 的最小生成树中的最大边权重，外加一个函数值 f(C) = c / |C|，其中 c 是一个正整数常量，|C| 是 C 的规模，即顶点个数；

• 如果一个顶点集合还能被划分为两个及以上的连通分量，则这个集合不能算做是一个连通分量。

你的任务就是列出所有连通分量。

输入格式

第一行输入三个整数：Nv（1 < Nv ≤ 1000）为顶点数量（顶点从 0 到 Nv - 1 编号）；Ne 为边的数量；c 是函数 f(C) 中的那个常数。随后 Ne 行，每行按以下格式给出一条边：顶点1编号 顶点2编号 权重。注意：题目保证每个像素点有不超过 8 个相邻的像素点。常数和所有的权重均不超过 1000。

输出格式

每行输出一个连通分量。每个连通分量的顶点要在一行中按编号升序输出，数字间以 1 个空格分隔，行首尾不得有多余空格。连通分量按照其首个顶点的升序输出。

输入样例1

10 21 100
0 1 10
0 3 60
0 4 90
1 2 90
1 3 50
1 4 200
1 5 86
2 4 95
2 5 5
3 4 95
3 6 15
3 7 101
4 5 500
4 6 100
4 7 101
4 8 101
5 7 300
5 8 50
6 7 90
7 8 84
7 9 34

输出样例1

0 1 3 6
2 5 8
4
7 9

输入样例2

7 7 100
0 1 10
1 2 61
2 3 50
3 4 200
4 5 82
5 0 200
3 6 90

输出样例2

0 1
2 3 6
4 5

限制

时间限制：1000ms，内存限制：64MiB