一个名为 Berland 的国家有 n 个城市。它们用 1 到 n 的整数编号。指数为 1 的城市是该国的首都。一些城市之间建有单向道路。然而,并非所有人都状况良好。对于每条道路,我们都知道它是否需要修复。如果道路需要维修,则禁止使用。不过,贝尔兰政府可以修复这条道路,使其可以使用。
现在贝兰德正受到与邻国的战争的威胁。于是京城官员决定向各城派出一支军队。这些小队只能沿着现有的道路移动,因为没有时间或金钱来修建新道路。然而,有些道路可能需要修复才能到达某些城市。
当然,这个国家需要大量的资源来击败敌人,所以你要小心你要投入的力量。这就是为什么贝尔兰政府希望修复最少数量的道路,足以让军队沿着良好或已修复的道路从首都到达任何城市。你的任务是帮助贝尔兰政府并找出哪些道路需要修复。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — Berland 的城市数量和道路数量。
接下来 m 行包含三个空格分隔的整数 ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 1),描述从城市 ai 到城市 bi 的道路。如果 ci 等于 0,则给定的道路状况良好。如果ci等于1,则需要修复。
保证每个方向的城市之间不超过一条道路。
输出
如果所有道路都修好后,仍然无法从首都到达某个城市,则打印 - 1。否则,在第一行打印需要修缮的最少道路数,在第二行打印这些道路的编号,以单个空格分隔。
道路按照输入中给出的顺序从 1 开始编号。
如果有多组,其中包括需要修复的最少数量的道路,以便可以从首都前往任何城市,请打印其中的任何一组。
如果可以沿着已经状况良好的道路行驶到达任何城市,则在唯一的输出行中打印 0。
示例
输入 #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