The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.
Given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The $$$i$$$-th edge connects vertex $$$u_i$$$ and vertex $$$v_i$$$ with traversal cost $$$w_i$$$.
Now, you may increase the traversal cost of all edges simultaneously by $$$k$$$, where $$$k$$$ is any non-negative real number. Question: how many distinct $$$^{\dagger}$$$ paths from vertex $$$1$$$ to vertex $$$n$$$ exist such that there is at least one value of $$$k$$$ for which that path is one of the shortest paths from $$$1$$$ to $$$n$$$?
$$$^{\dagger}$$$ Two paths are considered different if and only if they have different numbers of edges, or there exists an index $$$i$$$ such that the $$$i$$$-th edge on the two paths has a different edge index.
Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 1000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 5000$$$, $$$1 \leq m \leq 5000$$$), denoting the number of vertices and edges in the graph.
The next $$$m$$$ lines each contain three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$), describing an undirected edge between vertices $$$u_i$$$ and $$$v_i$$$ with traversal cost $$$w_i$$$.
For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$5000$$$.
For each test case, output a single integer — the number of paths that can become shortest paths from vertex $$$1$$$ to vertex $$$n$$$. Since the answer may be large, output it modulo $$$998\,244\,353$$$.
33 41 2 11 2 12 3 12 3 15 61 5 31 2 12 5 21 3 13 4 14 5 18 91 2 11 3 52 6 16 4 13 4 13 5 14 8 55 7 17 8 1
434
