文理学院程序设计在线练习


文字游戏

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 38   Accepted Submission(s): 10
Problem Description

最近小希在玩一款文字恋爱冒险类游戏(AVG),游戏有n个场景,初始场景为1,有些场景会有选项,不同的选项通往不同的场景。
游戏中,有一个女主角,不同的选项会影响与女主角的好感度,在初始场景中与女主角的好感度为0。
到达HappyEnd的前提是该场景为最终场景且至少有一种路线在到达该场景时与女主角的好感度大于等于100。
最终场景是指该场景没有选项通往其他场景。
问有多少个HappyEnd,且按顺序输出。
注意:可能有不同的场景会通过不同的选项到达同一个场景,但是不会有一种方法使得某场景经过一些选项回到自己(不会成环)。如果有一些场景永远无法从1到达,那么那些场景不计入答案(比如一些可以到达1的场景)。

Input

第一行输入一个整数T,表示数据组数(T<=100)。
每组数据第一行输入两个整数n,m(1 <= n,m<= 200000),分别代表场景数量和选项数量。
随后m行每行三个整数u,v,w(-1000 <= w <= 1000;1 <= u,v<= 200000),表示场景u有一个选项可以到达场景v,和女主角的好感度会加上w。

Output

对于每组数据输出2行;第一行输出一个整数p,表示HappyEnd的数量。
随后一行输出p个整数,分别为从小到大的HappyEnd场景的编号,数据之间留一个空格,如果p=0,该行请保持空行。注意:行末不要有多余空格。

Sample Input
2
2 1
1 2 99
5 4
1 2 150
2 3 -300
1 4 100
1 5 200
Sample Output
0

2
4 5
Hint

样例1中,最终场景只有2,此时与女主角的好感度为99,不满足HappyEnd条件。
样例2中,最终场景有3,4,5,与女主角的好感度分别为-150,100,200,其中4,5满足HappyEnd条件。

Source

2019校赛