你可能熟悉最小费用流问题。在最小费用流问题中，每条边 $e$ 都有一个费用 $c$；如果你在边上施加 $f$ 的流量，则使用该边的费用为 $cf$。换句话说，使用边的费用与你施加的流量成线性关系。这可能具有局限性。在某些应用中，使用不同类型的费用函数可能更好。

在本题中，你将解决这样一个变体：在一个网络中发送 1 单位流量，其中在边上施加流量的费用与流量的平方成正比。

形式化地，给定一个有向图，包含 $n$ 个顶点和 $m$ 条边。顶点编号为 $1 \dots n$，其中顶点 $1$ 是源点，顶点 $n$ 是汇点。对于每条边 $e$，给定一个非负费用 $c_e$。你需要为每条边 $e$ 确定一个实数 $f_e$：即流经该边的流量。数值 $f_e$ 必须满足以下条件：

• $\sum_{e \in \text{out}(1)} f_e - \sum_{e \in \text{in}(1)} f_e = 1$；
• $\sum_{e \in \text{out}(u)} f_e - \sum_{e \in \text{in}(u)} f_e = 0$，对于所有 $1 < u < n$；
• 在所有满足条件的方案中，$\sum_{e} c_e f_e^2$ 必须最小化。

注意，这里没有边容量限制。你可以根据需要为每条边分配任意流量。这里，$\text{out}(u)$ 和 $\text{in}(u)$ 分别表示顶点 $u$ 的出边集合和入边集合。允许将 $f_e$ 设置为负数，这表示流量沿相反方向流动。

你需要找到 $\sum_{e} c_e f_e^2$ 的最小值。可以证明，在本题的约束条件下，该值总是一个有理数。请输出该有理数对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例描述如下：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100, 1 \le m \le 300$)。

接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $c$ ($1 \le u, v \le n, 1 \le c < 998\,244\,353$)，表示一条从 $u$ 到 $v$ 且费用为 $c$ 的边。图中不存在自环、重边或反向重边。保证底层的无向图是连通的。

所有测试用例的 $n + m$ 之和不超过 $400$。

测试数据的构造方式保证至少存在一个最优流 $f$，使得对于每条边 $e$，$f_e$ 是一个可以表示为 $\frac{p}{q}$ 的有理数，其中 $p$ 和 $q$ 为整数且 $q \not\equiv 0 \pmod{998\,244\,353}$。

输出格式

对于每个测试用例，在单独的一行中打印答案——即问题答案对 $998\,244\,353$ 取模后的单个整数。

形式化地，令 $P = 998\,244\,353$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数。可以证明在本题的约束下，$q \not\equiv 0 \pmod P$。输出任意满足 $x \cdot q \equiv p \pmod P$ 的整数 $x$。

样例

输入 1

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

输出 1

1
665496236
713031683
614304219