TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

28.8% (34/118)

Tags

Description

海鞘對於草甘的精神狀況束手無策,便帶著草甘來到了古墨西哥神殿。

哪知海鞘一打開神殿的正門,便有一條巨大的觸手竄出,差點就要把海鞘捲走。
海鞘向當地村人打聽情報,才知道原來21年前這座神殿莫名出現了一隻大觸手,
使得想要進去探勘考古的烏龜提心吊膽。

這座神殿是由N間房間和M條雙向走廊所構成,每條走廊都有長度且兩間房間之間可能有不只一條走廊連接。
傳說中觸手總共佔領了N-1條走道,使得牠恰好能自由來往每間房間。
而且,觸手佔領的走道長度總和是所有可能佔領方案中最小的。

海鞘一聽大喜,這不就是最小生成樹(MST)嗎!
這樣就可以知道該避開哪些走廊了,但仔細想想才發現不對:最小生成樹並不唯一!
他只能找到一些走廊是無論如何都會被觸手佔領的。

無魚蝦也好,海鞘需要你告訴他有哪些走廊絕對會被觸手所佔領。

Input Format

輸入第一行有兩個數字N, M,表示房間數量跟走廊數量。(房間編號)
接下來有M行,每行有三個數字Ai, Bi, Ci,表示第i條走廊連接Ai, Bi,長度為Ci。

保證N ≤ 100,000,M ≤ 400,000,Ci可以用32位元有號整數貯存。

Output Format

輸出包含兩行,第一行是一定會被觸手佔領的走廊個數。
第二行由小到大輸出每條走廊編號,以空白作分隔。
如果沒有任何走廊,第二行請輸出單一一個"0"。

Sample Input

5 6
1 2 10
2 3 10
3 4 5
4 5 5
3 5 5
1 5 100

Sample Output

2
1 2

Hints

範例中有三種可能觸手:選擇走廊{1, 2, 3, 4}或{1, 2, 3, 5}或{1, 2, 4, 5}。

Problem Source

原TIOJ1698 / ABCLS Contest, Problem H

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144