# 较小权不完美非匹配

时间限制：0.5 秒；内存限制：128 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

“充分的准备永远不可能有行动！”

给你一张连通的无向带权图，你需要从顶点 $1$ 出发，访问每个顶点至少一次，再回到顶点 $1$ ，并按顺序给出经过的边。

不过，我们并不要求你找到最短的行走。题目已经准备了一个未必最优的预备方案，你的方案将按总边权与它的比较结果评分。请构造一个符合规则、能够拿到满分的方案。

## 形式化问题描述

给定有 $n$ 个顶点、$m$ 条边的连通无向带权图。顶点编号为 $1,\ldots,n$ ，边按输入顺序编号为 $1,\ldots,m$ .允许重边和自环。

输出一段边编号序列，使行走从顶点 $1$ 开始，沿这些边依次移动，访问每个顶点至少一次，最后回到顶点 $1$ .同一条边可以重复使用，但总使用次数不得超过 $5n$ .起点在行走开始时已算作访问；$n=1$ 时空行走合法。

令 $W$ 为图的最小生成树总权值，$B=2W$ .令合法输出的总边权为 $Y$ ，重复经过的边重复计权。每个测试点的百分制得分为

$$s(Y)=\begin{cases}100,&Y\le2B,\\40+\left\lceil\dfrac{60(5B-Y)}{3B}\right\rceil,&2B<Y\le5B,\\40,&Y>5B.\end{cases}$$

非法输出得零分。$B=0$ 时中间分支不可能出现：零费用合法行走得100分，其余合法行走得40分。各测试点的得分按下表权重相加。任务是输出能获得满分的合法行走。

## 输入格式

第一行 `n m` .接下来 $m$ 行，每行 `u v w` 表示一条端点为 $u,v$ 、权值为 $w$ 的无向边。

## 输出格式

第一行输出边的使用次数 $k$ .接下来 $k$ 行，每行输出一个边编号。允许任意满分解；样例输出不唯一。

## 样例 1

### 输入

```text
3 3
1 2 1
2 3 2
1 3 5
```

### 输出

```text
4
1
2
2
1
```

## 样例 2

### 输入

```text
1 0
```

### 输出

```text
0
```

## 样例 3

### 输入

```text
2 3
1 1 9
1 2 0
1 2 4
```

### 输出

```text
2
2
2
```

## 样例 4

### 输入

```text
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 3
```

### 输出

```text
5
1
2
3
4
5
```

## 样例解释

样例1选择权值为1和2的两条树边，各往返一次，总费用为6，等于基准 $B$ .样例2没有边，起点已经覆盖所有顶点。样例4的五条边形成合法闭路，费用为7，也能拿到满分。

![示意图](assets/example.svg)

加粗边构成最小生成树；边编号1、2依次往返即可覆盖三个顶点。

## 数据范围与分值

$1\le n\le10^5$ ，$n-1\le m\le2\cdot10^5$ ，$1\le u,v\le n$ ，$0\le w\le10^4$ .图连通。

| 分值 | 额外限制 |
| --- | --- |
| 20% | $n\le8,\ m\le15$ |
| 30% | $n\le1000,\ m\le3000$ |
| 50% | 无额外限制 |

共10个测试点，每点占10%；完整配方见[测试说明](tests/README.md)。