描述

我的一个朋友有一种独特的在城市中驾驶的方法，他说这有助于减少他必须记住的路线数量，以免迷路。他选择两个地点作为枢纽（$H1$和$H2$），将所有其他地点分配到$H1$或$H2$，然后学习从所有地点到其关联枢纽的最短路径。如果他想从$A$到$B$，他会从$A$到$A$关联的枢纽，然后到$B$关联的枢纽（如果$B$关联的枢纽与$A$不同），再到$B$。我的朋友总是会经过枢纽，即使这意味着他会多次访问目的地。

你的程序需要分析一个城市（一组节点和边长度），并选择最佳的枢纽对和节点分配方案。最佳配置是使所有节点对之间的平均旅行距离最小的配置。如果有多个配置得到相同的最低平均值，你的程序可以输出其中任何一个。

输入

输入包含多个测试用例。第一行是一个整数，表示测试用例的数量。

每个测试用例的第一行是： $n$ $m$ 其中 $2$ <= $n$ <= $100$ 和 $1$ <= $m$ <= $1000$。$n$ 是城市中的地点数量，$m$ 是直接连接两个地点的道路段数量。可能存在多条道路连接同一对地点，也可能有道路的起点和终点是同一地点。

接下来的 $m$ 行描述道路段，每行包含三个整数： $a$ $b$ $d$

其中 $1$ <= $a$ <= $n$，$1$ <= $b$ <= $n$，$1$ <= $d$ <= $1000$。$a$ 和 $b$ 是道路段的两个端点，$d$ 是从 $a$ 到 $b$（或 $b$ 到 $a$）的距离。所有道路都是双向的。

任意两个地点之间都存在路径。

输出

对于每个测试用例，输出一个最佳的枢纽选择和地点分配方案。输出一行包含 $n$ 个整数，用空格分隔。如果第 $i$ 个地点是枢纽，第 $i$ 个整数为 $0$；否则，第 $i$ 个整数为该地点的枢纽编号（$1$到 $n$ 之间）。

提示 输出字典序最小的序列。（例如，对于第一个测试用例，$2$ $0$ $0$ 也是有效的，但 $0$ $0$ $2$ 比 $2$ $0$ $0$ 小。）

选择$H1$和$H2$中编号较小的枢纽。

如果仍有多个解，输出字典序最小的序列。

输入数据 1

3
3 2
1 2 40
2 3 20
7 10
1 1 1
1 2 2
2 4 2
4 3 2
3 1 2
2 3 5
3 7 10
7 6 1
5 6 1
4 5 1
16 15
1 8 1
2 8 1
3 8 1
4 9 1
5 9 1
6 9 1
7 8 1
8 9 3
9 10 1
8 11 1
8 12 1
8 13 1
9 14 1
9 15 1
9 16 1

输出数据 1

0 0 2
4 4 4 0 0 5 5
8 8 8 9 9 9 8 0 0 9 8 8 8 9 9 9

来源

Mid-Atlantic 2004