The 4th(2009) ACM Programming Contest of HUST  Onsite Contest
From: 20091206 12:00:00
To: 20091206 17:00:00
Now: 20170920 01:08:28
Status: Public
B  Cheat Secretly
Time Limit: 1s
Memory Limit: 128MB
Submissions: 461 Solved: 158
 Description
 HH Big Cow(HBC) has taken part in an interesting treasure finding match.
In the match there are N transmitting nodes(labeled from 1 to N), and between these nodes there are M directional roads. In the middle of some roads there may be a “giftspot”, where a beautiful girl gives a gift to the contestant who passes that road. The one who gets most gifts wins!
Winning the match is so easy for HBC, so he is thinking of a more challenging thing —— collecting gifts from ALL the girls. HBC has an amazing ability to achieve this goal: When he comes to a dead end, he can transfer himself to another node arbitrarily.
With that ability, of course he can achieve the goal of meeting all the girls, however, cheating is not good! So he decides to use the ability as few as possible. Now he wants to know the fewest times he should use that ability to achieve his goal.
NOTE:
1. The graph in the match is a directed acyclic graph (DAG).
2. There is at most one road between any two nodes.
 Input
 The input contains multiple case.
Line 1 an integer T : number of test cases.
Line 2 two integer N, M:
N for number of nodes. (2 <= N <= 500)
M for number of roads. (1 <= M <= 10000)
Lines 3..M+2 each line three integers a, b, c: representing a directed roads from a to b. (1 <= a, b <= N)
c = 1, then there is a gift spot on this road.
c = 0, then there is no gift spot on this road.
 Output
 For each case output one line representing the fewest number of ability HBC should use.
 Sample Input

2
4 2
1 2 1
3 4 1
6 7
1 2 1
2 3 1
3 4 1
1 4 0
5 2 1
3 6 1
5 6 0
 Sample Output

Case #1: 2
Case #2: 2
 Hint
 Source
 Yang Xiaobin, HUST Campus 2009