【题目描述】

在Benelux这个神奇的国度里，“你的个人假期”旅行团组织了一系列旅车观光游览活动。假设Benelux是一个N个点M条边的有向带权图，旅车从S点出发到达T点。在旅车行驶过程中，旅车内的乘客可以尽情观赏沿途的美景，或者在一些风景优美的城市里停顿一小会并下车休息。 不同的旅客对不同的美景比较偏爱，因此旅行团将要在多个旅行路线中精心挑选。在预定好旅馆之后，乘客们从点S移向点T。从S到T的两条路径被认作不同，当且仅当存在一条单向边，在其中一条路径中，而不在另一条内。

乘客们选择的路径有一条限制：为了留出更多的时间给乘客在下车点处自由休息（其实是为了省油），旅车行驶的路径，与最短路的差值不能超过1。

举个例子，在上图中1->2->5和1->3->5是被认为最短的，长度为6。而路径1->3->4->5的长度为7，与最短路的差值仅为1，也是可取的。

现在，给你这个有向带权图，“你的个人假期”旅行团想知道，有多少条不同的路径满足以上要求，及最短路或只比最短路相差1的次短路？

【输入格式】

第一行为一个正整数case，表示输入数据分为case组。 对于每一组数据，第一行为两个正整数N,M。

接下来M行每行三个正整数i,j,dis，表示从i到j有一条长度为dis的边。

【输出格式】

输出共case行，每一行代表一组数据，为所求的答案。

【样例输入/输出】

Sample input(sightseeing.in)

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

Sample output(sightseeing.out)

3
2

【数据范围】

测试点 case N M dis

[ 1, 6] <=10 <=1000 <=10000 <=1000

[ 7,10] <=20000 <=100000