Tomya is a girl. She loves Chef Ciel very much.

Today, too, Tomya is going to Ciel's restaurant.
Of course, Tomya would like to go to Ciel's restaurant as soon as possible.
Therefore Tomya uses one of the shortest paths from Tomya's house to Ciel's restaurant.
On the other hand, Tomya is boring now to use the same path many times.
So Tomya wants to know the number of shortest paths from Tomya's house to Ciel's restaurant.
Your task is to calculate the number under the following assumptions.

This town has N intersections and M two way roads.
The i-th road connects from the Ai-th intersection to the Bi-th intersection, and its length is 

Ci.
Tomya's house is in the 1st intersection, and Ciel's restaurant is in the N-th intersection.

-----Input-----

The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line of each test case contains 2 integers N, M.
Then next M lines contains 3 integers denoting Ai, Bi and Ci.

-----Output-----

For each test case, print the number of shortest paths from Tomya's house to Ciel's restaurant.

-----Constraints-----

1 ≤ T ≤ 10

2 ≤ N ≤ 10

1 ≤ M ≤ N ∙ (N – 1) / 2

1 ≤ Ai, Bi ≤ N

1 ≤ Ci ≤ 10
Ai ≠ Bi

If i ≠ j and Ai = Aj, then Bi ≠ Bj

There is at least one path from Tomya's house to Ciel's restaurant.

-----Sample Input-----
2
3 3
1 2 3
2 3 6
1 3 7
3 3
1 2 3
2 3 6
1 3 9

-----Sample Output-----
1
2

-----Explanations-----

In the first sample, only one shortest path exists, which is 1-3.

In the second sample, both paths 1-2-3 and 1-3 are the shortest paths.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
def snek(k, n, x, d, g):
	if k == n:
		x += [d[n]]
		return
	for i in range(1, n + 1):
		if g[k][i] != 0 and d[i] == -1:
			d[i] = d[k] + g[k][i]
			snek(i, n, x, d, g)
			d[i] = -1
t = int(input())
for i in range(t):
	g = [[0 for i in range(11)] for j in range(11)]
	(v, e) = map(int, input().split())
	for j in range(e):
		(x, y, w) = map(int, input().split())
		g[x][y] = w
		g[y][x] = w
	x = []
	d = [-1] * (v + 1)
	d[1] = 0
	snek(1, v, x, d, g)
	x.sort()
	r = x[0]
	ans = 0
	for z in range(len(x)):
		if r == x[z]:
			ans += 1
	print(ans)


def check(k, n, x1, d, g):
	if k == n:
		x1 += [d[n]]
		return
	for i in range(1, n + 1):
		if g[k][i] != 0 and d[i] == -1:
			d[i] = d[k] + g[k][i]
			check(i, n, x1, d, g)
			d[i] = -1
testCases = int(input())
while testCases > 0:
	testCases = testCases - 1
	dimension = list(map(int, input().strip().split(' ')))
	v = dimension[0]
	e = dimension[1]
	graph = [[0 for i in range(11)] for j in range(11)]
	for i in range(e):
		(a, b, c) = map(int, input().split())
		graph[a][b] = c
		graph[b][a] = c
	x1 = []
	d = [-1] * (v + 1)
	d[1] = 0
	check(1, v, x1, d, graph)
	x1.sort()
	r = x1[0]
	s = 0
	for i in range(len(x1)):
		if r == x1[i]:
			s += 1
	print(s)


t = int(input())

def func(k, n, x, dist, graph):
	if k == n:
		x += [dist[n]]
		return
	for i in range(1, n + 1):
		if graph[k][i] != 0 and dist[i] == -1:
			dist[i] = dist[k] + graph[k][i]
			func(i, n, x, dist, graph)
			dist[i] = -1
while t:
	graph = [[0 for i in range(11)] for j in range(11)]
	(v, e) = map(int, input().split())
	for i in range(e):
		(x, y, w) = map(int, input().split())
		graph[x][y] = w
		graph[y][x] = w
	x = []
	dist = [-1] * (v + 1)
	dist[1] = 0
	func(1, v, x, dist, graph)
	x.sort()
	val = x[0]
	ans = 0
	for i in range(len(x)):
		if val == x[i]:
			ans += 1
	print(ans)
	t -= 1


t = int(input())

def check(k, n, x1, d, g):
	if k == n:
		x1 += [d[n]]
		return
	for i in range(1, n + 1):
		if g[k][i] != 0 and d[i] == -1:
			d[i] = d[k] + g[k][i]
			check(i, n, x1, d, g)
			d[i] = -1
for i in range(t):
	(v, e) = map(int, input().split())
	g = [[0 for i in range(11)] for j in range(11)]
	for i in range(e):
		(x, y, w) = map(int, input().split())
		g[x][y] = w
		g[y][x] = w
	x1 = []
	d = [-1] * (v + 1)
	d[1] = 0
	check(1, v, x1, d, g)
	x1.sort()
	r = x1[0]
	s = 0
	for i in range(len(x1)):
		if r == x1[i]:
			s += 1
	print(s)


def DFS(start, n, path_w, dist, adj):
	if start == n:
		path_w += [dist[n]]
		return
	for i in range(1, n + 1):
		if adj[start][i] != 0 and dist[i] == -1:
			dist[i] = dist[start] + adj[start][i]
			DFS(i, n, path_w, dist, adj)
			dist[i] = -1

def func():
	(n, m) = map(int, input().split(' '))
	adj = [[0 for j in range(n + 1)] for i in range(n + 1)]
	dist = [-1 for i in range(n + 1)]
	path_w = []
	for i in range(m):
		(x, y, w) = map(int, input().split(' '))
		adj[x][y] = w
		adj[y][x] = w
	dist[1] = 0
	DFS(1, n, path_w, dist, adj)
	path_w.sort()
	maxm = path_w[0]
	ans = path_w.count(maxm)
	print(ans)
t = int(input())
while t:
	func()
	t -= 1


import heapq
Graph = []
N = 0

def dijkstras():
	Q = []
	visitedCount = [0] * N
	dist = [float('inf')] * N
	heapq.heappush(Q, tuple([0, 0]))
	dist[0] = 0
	visitedCount[0] = 1
	while len(Q) > 0:
		(curDist, curNode) = heapq.heappop(Q)
		for (nextNode, weight) in Graph[curNode]:
			nextDist = curDist + weight
			if nextDist == dist[nextNode]:
				visitedCount[nextNode] += visitedCount[curNode]
			elif nextDist < dist[nextNode]:
				visitedCount[nextNode] = visitedCount[curNode]
				dist[nextNode] = nextDist
				heapq.heappush(Q, (nextDist, nextNode))
	return visitedCount[N - 1]

def main():
	nonlocal N
	nonlocal Graph
	T = int(input())
	for test in range(T):
		(N, M) = tuple(map(int, input().split()))
		Graph = []
		for x in range(N):
			Graph.append([])
		for edge in range(M):
			(Ai, Bi, Ci) = tuple(map(int, input().split()))
			Graph[Ai - 1].append((Bi - 1, Ci))
			Graph[Bi - 1].append((Ai - 1, Ci))
		print(dijkstras())

def __starting_point():
	main()
__starting_point()


t = int(input())

def check(start, n, path, dis, adj):
	if start == n:
		path += [dis[n]]
		return
	for i in range(1, n + 1):
		if adj[start][i] != 0 and dis[i] == -1:
			dis[i] = dis[start] + adj[start][i]
			check(i, n, path, dis, adj)
			dis[i] = -1
for i in range(t):
	(v, e) = map(int, input().split())
	adj = [[0 for i in range(11)] for j in range(11)]
	for i in range(e):
		(x, y, w) = map(int, input().split())
		adj[x][y] = w
		adj[y][x] = w
	path = []
	dis = [-1] * (v + 1)
	dis[1] = 0
	check(1, v, path, dis, adj)
	path.sort()
	maxi = path[0]
	result = 0
	for i in range(len(path)):
		if maxi == path[i]:
			result += 1
	print(result)