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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import heapq\n\n\nGraph = []\nN = 0\ndef dijkstras():\n Q = []\n visitedCount = [0]*N\n dist = [float("inf")]*N\n heapq.heappush(Q, tuple([0, 0]) )\n dist[0] = 0\n visitedCount[0] = 1\n while len(Q) > 0:\n  curDist, curNode = heapq.heappop(Q)\n  for (nextNode, weight) in Graph[curNode]:\n   nextDist = curDist + weight\n   if nextDist == dist[nextNode]:\n    visitedCount[nextNode] += visitedCount[curNode]\n   elif nextDist < dist[nextNode]:\n    visitedCount[nextNode] = visitedCount[curNode]\n    dist[nextNode] = nextDist\n    heapq.heappush(Q, (nextDist, nextNode))\n\n return visitedCount[N-1]\n\ndef main():\n nonlocal N\n nonlocal Graph\n T = int(input())\n for test in range(T):\n  N, M = tuple( map(int, input().split()) )\n  Graph = []\n  for x in range(N): Graph.append([])\n  for edge in range(M):\n   Ai, Bi, Ci = tuple( map(int, input().split()) )\n   Graph[Ai-1].append((Bi-1, Ci))\n   Graph[Bi-1].append((Ai-1, Ci))\n\n  print(dijkstras())\n\ndef __starting_point():\n main()\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: