← 返回题目列表

AtCoder · iroha2019_day2_d

D. 家庭园艺真是太有趣了

中文机器翻译题面 查看原题

配点: 400 点

問題文

*Kitamu 是帮助撰写此问题的人的名字。而且,Kitamu的女朋友不是伊吕波。

Kitamu 的爱好是园艺。北穆哈 您有 N 个底池,每个底池有 它的编号为 1~N 。另外,水不足的地方,水会自动流入锅内。 M 一条水路连接着盆栽,水路 i 是一个锅 A_i 和锅 B_i已连接。还有水路 i 是1以秒为单位 C_i 分升的水可以双向流动。请注意,您可以从一个盆地经过几条水道到达所有不同的盆地。

嗯,Kitamu 和她的关系进展顺利,她最终来到了 Kitamu 家。为了展现自己朴素的一面,Kitamu比平时更加细心地照顾花朵。

但是! ! !

我添加了太多的通道来改善水流,我意识到这非常笨拙。长此以往,人们会认为我是一个不爱干净的人。因此,我们在拆除部分水道时,注意以下几点。水道数量最小化我决定这么做。

  • 保持一个盆可以通过几条水道到达所有不同盆的状态。
  • 可以倒入每个剩余的水道中总水量最大化做

你突然想知道北梦留下的水道是哪条,所以你决定通过程序计算来找到它。

制約

  • 所有输入均为整数
  • 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

出力

按升序输出Kitamu留下的水道编号,并以换行符分隔。

在这个问题的约束下,答案总是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

解説

解説