H. Minimum Cost Flow²
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You may be familiar with the minimum cost flow problem. In the minimum cost flow problem, every edge $$$e$$$ has a cost $$$c$$$; if you put $$$f$$$ flow on that edge, you have to pay $$$cf$$$ for using that edge. In other words, the cost of using an edge is linear in the amount of flow you put on it. This may be limiting. Maybe in some applications it is better to use a different kind of cost function.

In this problem you will solve one such variant: the cost of sending 1 unit of flow through a network where the cost of putting flow on an edge is quadratic in the amount of flow you put on it.

Formally, you are given an directed graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are indexed $$$1 \ldots n$$$, where vertex 1 is the source and vertex $$$n$$$ is the sink. For each edge $$$e$$$, you are given a nonnegative cost $$$c_e$$$. You have to decide, for each edge $$$e$$$, a real number $$$f_e$$$: the amount of flow running through this edge. The numbers $$$f_e$$$ must satisfy the following:

  • $$$\displaystyle \sum_{e \in \text{out} (1)} f_e - \sum_{e \in \text{in} (1)} f_e = 1$$$;
  • $$$\displaystyle \sum_{e \in \text{out} (u)} f_e - \sum_{e \in \text{in} (u)} f_e = 0$$$ for all $$$1 \lt u \lt n$$$;
  • Among all valid choices, $$$\displaystyle \sum_e c_e f^2_e$$$ must be minimized.

Notice that there are no edge capacities. You may put as much flow on each edge as you like. Here, $$$\text{out} (u)$$$ and $$$\text{in} (u)$$$ represent the sets of outgoing and incoming edges to vertex $$$u$$$, respectively. You are allowed to set $$$f_e$$$ to a negative number, this represents flow going in the opposite direction.

You have to find the minimum possible value of $$$\sum_e c_e f^2_e$$$. It can be proven that under the constraints of this problem, this is always a rational number. Output this rational number modulo $$$998\,244\,353$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. $$$t$$$ test cases follow. Each test case is described as follows.

The first line of the test case consists of two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100$$$, $$$1 \le m \le 300$$$).

Each of the following $$$m$$$ lines consists of three integers $$$u$$$, $$$v$$$ and $$$c$$$ ($$$1 \le u, v \le n$$$, $$$1 \le c \lt 998\,244\,353$$$), representing an edge from $$$u$$$ to $$$v$$$ with cost $$$c$$$. There are no self-loops, parallel or antiparallel edges. It is guaranteed that the underlying undirected graph is connected.

The sum of $$$n + m$$$ over all test cases doesn't exceed 400.

The tests are constructed in such a way that there exists at least one optimal flow $$$f$$$, such that for each edge $$$e$$$, $$$f_e$$$ is a rational number that can be expressed as $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0 \pmod{998\,244\,353}$$$.

Output

For each test case, print the answer on a separate line — a single integer, the answer to the problem modulo $$$998\,244\,353$$$.

Formally, let $$$P = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers. It can be shown that under the constraints of this problem, $$$q \not\equiv 0 \pmod{P}$$$. Output any integer equal to $$$p \cdot q^{-1} \pmod{P}$$$. In other words, output an integer $$$x$$$ so that $$$-2^{31} \le x \lt 2^{31}$$$ and $$$x \cdot q \equiv p \pmod{P}$$$.

Example
Input
4
4 4
1 2 1
2 4 1
1 3 1
3 4 1
3 3
1 2 1
1 3 1
2 3 1
5 6
1 2 1
2 3 3
2 4 1
3 4 1
3 5 1
1 5 8
4 5
1 2 1
1 3 2
2 3 1
3 4 1
4 2 8
Output
1
665496236
713031683
614304219