题目描述

Berland 有 $N$ 座城市和 $M$ 条双向道路。任意两座城市之间至多有一条道路，并且原图连通。

敌军计划突然占领其中一座城市。被占领的城市无法再被 Berland 军队通过。与此同时，恐怖分子可以提前破坏若干道路；破坏第 $i$ 条道路需要花费 $w_i$。

敌方希望通过“破坏道路 + 随后占领某一座城市”把 Berland 分成至少两个互不连通的部分。

形式化地说，你需要选择一些道路进行破坏，使得 存在至少一座城市 $c$，当城市 $c$ 被占领后，在所有未被破坏的道路中，至少存在两座未被占领的城市彼此不可达。

请找出破坏道路的最小总代价，并输出任意一种最优的道路集合。

注意：你不需要输出最终被占领的是哪座城市。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含三个整数 $a_i,b_i,w_i$，表示城市 $a_i$ 与 $b_i$ 之间有一条双向道路，破坏费用为 $w_i$。

道路按照输入顺序编号为 $1\sim M$。

数据范围：

• $3\le N\le50$；
• $1\le M\le500$；
• $1\le a_i<b_i\le N$；
• $1\le w_i\le10$；
• 无重边；
• 原图连通。

输出格式

第一行输出最小总代价。

第二行输出需要破坏的道路数 $K$。

第三行输出这 $K$ 条道路的编号，以空格分隔。

若 $K=0$，第三行可以为空行。

如果最优方案不唯一，输出任意一种即可。

样例 1

3 3
1 2 1
2 3 2
1 3 2

1
1
1

样例 2

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

2
2
2 4