問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

きたむーは家庭菜園が趣味である。きたむーは $N$ 個のポットを所持していて、各ポットには $1～N$ の番号が振られている。また、水が不足したポットに自動で水が流れるよう、 $M$ 本の水路がポットを繋いでおり、水路 $i$ はポット $A_i$ とポット $B_i$を繋いでいる。また、水路 $i$ は$1$秒間に $C_i$ デシリットルの水を双方向に流すことができる。なお、あるポットから異なるすべてのポットに対して、何本かの水路を経由することでたどり着くことができる。

さて、きたむーと彼女の関係は順調に進展し、なんと彼女がきたむーの家に来ることになった。きたむーは自分の家庭的な面を見せるため、いつも以上に丁寧にお花さんたちの世話をしていた。

が、しかし！！！

水の流れをよくするためにと水路を増やしすぎて、非常に不格好であることに気が付いた。このままでは片づけができない人間だと思われてしまう。そこで、以下の点を気を付けていくつかの水路を取り除き、水路の数を最小化することにした。

• あるポットから異なるすべてのポットに対して、何本かの水路を経由することでたどり着くことができる状態を保つ
• 残った各水路に流すことができる水の量の総和を最大化する

あなたはきたむーがどの水路を残したのかふと気になったので、プログラム計算によって求めることにした。

制約

• 入力はすべて整数
• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq M \\leq 4 \\times 10^5$
• $1 \\leq A_i,B_i \\leq N$ $(1 \\leq i \\leq M)$
• $A_i \\neq B_i$ $(1 \\leq i \\leq M)$
• $1 \\leq C_i \\leq 10^9$ $(1 \\leq i \\leq M)$
• $C_i \\neq C_j$ $(1 \\leq i,j \\leq M$ かつ $i \\neq j)$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\\vdots$ $A_M$ $B_M$ $C_M$

出力

きたむーが残した水路の番号を昇順かつ改行区切りで出力せよ。

この問題の制約のもとで答えは必ず$1$つであることが証明できる。(2019/05/01 13:25 追記)

入力例 1

5 10
4 1 45
4 2 48
5 3 72
1 4 93
5 1 32
1 3 56
5 1 38
5 4 41
5 2 6
5 1 19

出力例 1

2
3
4
6

入力例 2

5 8
1 4 72
2 1 52
1 3 10
5 3 7
3 4 37
3 2 47
4 1 82
5 3 57

出力例 2

2
6
7
8

解説

解説