题目描述

$\text{M}$ 超星系因为资源争夺即将爆发第四次星际战争，星系管理委员会为了避免此次战争的爆发，召集具有智慧生物的星球各派出一名大使于 $\text{Z}$ 星球进行协商谈判。

参加此次协商谈判的大使共有 $n$ 名，依次来自星球 $1$ 至星球 $n$。来自星球 $i$ 的大使与来自星球 $j$ 的大使，要么互相认识，要么互相不认识。由于历次战争的缘故，来自星球 $i$ 的大使对来自星球 $j$ 的大使的厌恶度为 $h_{i,j}$，来自星球 $j$ 的大使对来自星球 $i$ 的大使的厌恶度为 $h_{j,i}$。注意，可能 $h_{i,j} \ne h_{j,i}$。

现在需要为每位大使安排晚宴的座位。餐桌是圆形的，为了尽量融洽晚宴的气氛，要求餐桌上相邻两位大使互相认识且每张餐桌至少有两位大使。定义一张餐桌的不和谐度—— 按照顺时针方向，相邻两位大使的厌恶度之和。例如，某张餐桌按照顺时针方向依次坐着来自星球 $1$、星球 $3$、星球 $7$、星球 $10$ 的大使，则该张餐桌的不和谐度：

$$H=h_{1,3}+h_{3,7}+h_{7,10}+h_{10,1}$$

试确定是否存在满足要求的座位安排，如果存在，确定所有餐桌不和谐度之和的最小值并输出任意一种符合要求的座位安排方案。

输入格式

测试数据的第一行为两个整数 $n$，$m$。$n$ 表示大使的数量。接下来 $m$ 行数据，每行包含三个整数 $i$，$j$, $h_{i,j}$，表示来自第 $i$ 个星球的大使对来自第 $j$ 个星球的大使的厌恶度为 $h_{i,j}$。

只要来自第 $i$ 个星球的大使和来自第 $j$ 个星球的大使互相认识，就会给出厌恶度，否则不会给出厌恶度。互相认识的大使之间的厌恶度数据只会给出一次，不会重复给出。

输出格式

如果不存在满足题意要求的座位安排，输出 Impossible!。否则输出一行，包含一个整数，表示所有餐桌不和谐度之和的最小值。然后，给出任意一种符合题目要求的餐桌座位安排方案，即输出若干行，每行表示一张餐桌的座位安排方案，按照顺时针方向的顺序，打印大使所来自星球的编号。编号之间以空格分隔。

输入输出样例

4 6
1 2 1
2 1 2
1 3 3
3 1 4
2 3 5
3 2 6

Impossible!

4 12
1 2 1
2 1 2
1 3 10
3 1 10
1 4 10
4 1 10
2 3 10
3 2 10
2 4 10
4 2 10
3 4 3
4 3 4

10
1 2
3 4

说明/提示

子任务测试采用捆绑方式计分。

样例说明

• 对于输入数据 $1$，由于来自星球 $4$ 的大使与其他三位大使均不认识，所以无法安排座位。

• 对于输入数据 $2$，将来自星球 $1$ 和星球 $2$ 的大使安排在一桌，将来自星球 $3$ 和星球 $4$ 的大使安排在另一桌，不和谐度之和最小，为 $10$。

---

数据范围

• $\texttt{Subtask 1(10 pts)}$：$2 \le n \le 5$。
• $\texttt{Subtask 2(20 pts)}$：$2 \le n \le 10$。
• $\texttt{Subtask 3(40 pts)}$：$2 \le n \le 200$。
• $\texttt{Subtask 4(30 pts)}$：$2 \le n \le 700$。

对于 $100\%$ 的数据，$2 \le n \le 700$，$0 \le m \le n(n-1)$，$0 \le h_{i,j} \le 10^9$。

---

提示

本题提供 $\texttt{Special Judge}$ 源文件 和 checker.exe，使用方法为:
命令行在目标文件夹输入指令：

checker.exe input.txt output.txt output.txt

其中 input.txt 是输入数据文件，output.txt 是程序运行结果文件。观察评判结果给出的特判退出代码即可。

特判退出代码的含义：
0 - 用户输出与参考输出符合。
1 - 判断是否存在符合要求的座位安排方案时发生错误或输出错误的最小不和谐度值。
2 - 输出格式错误，包含非数字字符。
3 - 大使的索引超出范围。
4 - 某位大使出现在两张餐桌上。
5 - 在餐桌上相邻的两位大使互相不认识。
6 - 某位大使没有座位。
7 - 座位安排方案的不和谐度不是最小值。

请务必保证输出格式正确，否则 $\texttt{Special Judge}$ 可能会返回 $\texttt{Unkown Error}$ 等不可预估的结果。