War

In the war between Anihc and Bandzi, Anihc has won Bangzi. At that time, Lvbin, the king of Anihc, want to start from Bangzi to beat Nebir across the channel between them. He let his army get to there as soon as possible, and there located many islands which can be used to have a break. In order to save time, the king forbid the army getting through the same pass for more than one time, but they can reach the same island for as many as times they want.
Yunfeng, the General of the army, must tell how many optimal ship routes are there to the king as soon as possible, or he will be killed. Now he asks for your help. You must help Yunfeng to save his life.
He tells you that there are N island. The islands are numbered from 1 to N(1 is Bangzi and N is Nebir, others are many islands). And there are many ways, each way contain the islands number U and V and the length W. Please output your answer.

The first line in the input file contains a single integer number T means the case number.
Each case contains a number N (N<=1500) means the number of the islands.
And then many lines follow. Each line contains three numbers: U V W (W<10000), means that the distance between island U and V is W. The input of ways are terminated by “ 0 0 0 ”.

Print the number of the optimal ship routes are there after each case in a line.

1
6
1 2 1
3 2 1
3 4 1
1 3 2
4 2 2
4 5 1
5 6 1
4 6 2
0 0 0

2

alpc92

2010 ACM-ICPC Multi-University Training Contest（16）——Host by NUDT