Road Repairs

题意翻译

一个名叫 Berland 的国家有 $n$ 个城市，它们被从 $1$ 到 $n$ 的整数编号。编号为 $1$ 的城市是这个国家的首都。一些城市两两之间有一条单向道路。然而，不是所有的路都是完好的。对于每一条路我们都知道是否需要修复。如果一条路需要修复，那么它就禁止被使用。但是，Berland 的政府可以修复道路然后这条路就可以用了。 现在 Berland 正在受到邻国战争的威胁。所以首都的官员决定往每个城市送一支军队。如果他们没有钱或者时间去建一条新路那么这些军队只能够通过完好的道路。然而，为了到达一些城市一些道路可能可以修复好。 当然国家需要很多的资源去战胜敌人，所以你想要小心地计划投入军队的资源。这就是 Berland 的政府想要尽可能地修复好最少的道路让军队能从首都到每一个城市的原因，给你一些路并告诉你这条路是好的还是要修复的。你的任务就是帮助 Berland 政府并找出哪些路需要被修复。 输入格式： 第一行有两个整数 $n,m$（$1 \leq n,m \leq 10^5$）——城市的数量和 Berland 的道路的数量。 接下来 $m$ 行包括 $3$ 个整数 $a_i$，$b_i$，$c_i$（$1 \leq a_i,b_i \leq n$ ，$a_i \neq b_i$，$0 \leq c_i \leq 1$），描述的是一条从 $a_i$ 到 $b_i$ 的道路，如果 $c_i$ 等于 0，那么给的这条路就是好的；如果 $c_i$ 等于 1，那么 给的这条路就是需要修理的。 保证没有重边。 输出格式： 如果修复了所有的道路以后还是不能到达每个城市，输出-1。否则，第一行输出有几条路需要修复，第二行输出需要修复的路的编号，用一个空格隔开。 道路从 1 开始编号，在输入中给出。 如果有多种方案，请输出任意一种。如果所有路都是好的，请只在第一行输出 0。

题目描述

A country named Berland has $ n $ cities. They are numbered with integers from $ 1 $ to $ n $ . City with index $ 1 $ is the capital of the country. Some pairs of cities have monodirectional roads built between them. However, not all of them are in good condition. For each road we know whether it needs repairing or not. If a road needs repairing, then it is forbidden to use it. However, the Berland government can repair the road so that it can be used. Right now Berland is being threatened by the war with the neighbouring state. So the capital officials decided to send a military squad to each city. The squads can move only along the existing roads, as there's no time or money to build new roads. However, some roads will probably have to be repaired in order to get to some cities. Of course the country needs much resources to defeat the enemy, so you want to be careful with what you're going to throw the forces on. That's why the Berland government wants to repair the minimum number of roads that is enough for the military troops to get to any city from the capital, driving along good or repaired roads. Your task is to help the Berland government and to find out, which roads need to be repaired.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ — the number of cities and the number of roads in Berland. Next $ m $ lines contain three space-separated integers $ a_{i},b_{i},c_{i} $ $ (1<=a_{i},b_{i}<=n,a_{i}≠b_{i},0<=c_{i}<=1) $ , describing the road from city $ a_{i} $ to city $ b_{i} $ . If $ c_{i} $ equals $ 0 $ , than the given road is in a good condition. If $ c_{i} $ equals $ 1 $ , then it needs to be repaired. It is guaranteed that there is not more than one road between the cities in each direction.

输出格式

If even after all roads are repaired, it is still impossible to get to some city from the capital, print $ -1 $ . Otherwise, on the first line print the minimum number of roads that need to be repaired, and on the second line print the numbers of these roads, separated by single spaces. The roads are numbered starting from $ 1 $ in the order, in which they are given in the input. If there are multiple sets, consisting of the minimum number of roads to repair to make travelling to any city from the capital possible, print any of them. If it is possible to reach any city, driving along the roads that already are in a good condition, print $ 0 $ in the only output line.

输入输出样例

输入样例 #1

3 2
1 3 0
3 2 1

输出样例 #1

1
2

输入样例 #2

4 4
2 3 0
3 4 0
4 1 0
4 2 1

输出样例 #2

-1

输入样例 #3

4 3
1 2 0
1 3 0
1 4 0

输出样例 #3

0

题意翻译

一个名叫 Berland 的国家有 $n$ 个城市，它们被从 $1$ 到 $n$ 的整数编号。编号为 $1$ 的城市是这个国家的首都。一些城市两两之间有一条单向道路。然而，不是所有的路都是完好的。对于每一条路我们都知道是否需要修复。如果一条路需要修复，那么它就禁止被使用。但是，Berland 的政府可以修复道路然后这条路就可以用了。 现在 Berland 正在受到邻国战争的威胁。所以首都的官员决定往每个城市送一支军队。如果他们没有钱或者时间去建一条新路那么这些军队只能够通过完好的道路。然而，为了到达一些城市一些道路可能可以修复好。 当然国家需要很多的资源去战胜敌人，所以你想要小心地计划投入军队的资源。这就是 Berland 的政府想要尽可能地修复好最少的道路让军队能从首都到每一个城市的原因，给你一些路并告诉你这条路是好的还是要修复的。你的任务就是帮助 Berland 政府并找出哪些路需要被修复。 输入格式： 第一行有两个整数 $n,m$（$1 \leq n,m \leq 10^5$）——城市的数量和 Berland 的道路的数量。 接下来 $m$ 行包括 $3$ 个整数 $a_i$，$b_i$，$c_i$（$1 \leq a_i,b_i \leq n$ ，$a_i \neq b_i$，$0 \leq c_i \leq 1$），描述的是一条从 $a_i$ 到 $b_i$ 的道路，如果 $c_i$ 等于 0，那么给的这条路就是好的；如果 $c_i$ 等于 1，那么 给的这条路就是需要修理的。 保证没有重边。 输出格式： 如果修复了所有的道路以后还是不能到达每个城市，输出-1。否则，第一行输出有几条路需要修复，第二行输出需要修复的路的编号，用一个空格隔开。 道路从 1 开始编号，在输入中给出。 如果有多种方案，请输出任意一种。如果所有路都是好的，请只在第一行输出 0。