CF1100E Andrew and Taxi

Andrew 更喜欢打车而不是使用其他交通工具，但最近大多数出租车司机行为不端。为了赚更多的钱，出租车司机开始绕圈行驶。Andrew 所在城市的道路是单向的，并且人们不一定能够从一个地方到达另一个地方，但与狡猾的出租车司机相比，这些都不算什么。 市长决定改变某些道路的方向，这样出租车司机就无法无限制地增加行程费用。更正式地说，如果出租车司机在某个路口出发，在进行非零次行驶后，他将无法再次回到该路口。 需要交通管理员来改变道路的行驶方向。对于每条道路，已知需要多少名交通管理员才能将其方向反转。允许逐条道路地改变方向，也就是说，每个交通管理员可以参与反转两条或更多的道路。 你需要计算完成该任务所需雇佣的最少交通管理员数量，以及需要反转方向的道路列表。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100\,000$，$1 \leq m \leq 100\,000$），分别表示城市中的路口数量和道路数量。 接下来的 $m$ 行中，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \leq u_i, v_i \leq n$，$1 \leq c_i \leq 10^9$，$u_i \ne v_i$），表示第 $i$ 条道路起点为 $u_i$，终点为 $v_i$，反转该道路所需的交通管理员数量。

第一行输出两个整数，分别表示完成任务所需的最少交通管理员数量，以及需要反转方向的道路数量 $k$。$k$ 不需要最小化。 第二行输出 $k$ 个用空格分隔的整数，表示需要反转方向的道路编号。道路按输入顺序从 $1$ 开始编号。如果有多种方案，输出任意一种均可。

在第一个样例中，有两个简单环：$1 \rightarrow 5 \rightarrow 2 \rightarrow 1$ 和 $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$。一个交通管理员只能反转道路 $2 \rightarrow 1$，但无法单独破坏第二个环。两个交通管理员可以分别反转道路 $2 \rightarrow 1$ 和 $2 \rightarrow 3$，这样就能满足条件。 在第二个样例中，一个交通管理员无法破坏环 $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$。通过三个交通管理员，我们可以例如反转道路 $1 \rightarrow 3$、$2 \rightarrow 4$、$1 \rightarrow 5$。 由 ChatGPT 4.1 翻译