TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

83.9% (26/31)

Submission's AC Ratio

28.9% (65/225)

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 1

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

Sample Output 1

2
1 2

Hints

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

Problem Source

原TIOJ1698 / ABCLS Contest, Problem H

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10