题目描述

小 $A$ 是社团里的工具人，有一天他的朋友给了他一个$n$个点，$m$ 条边的正权连通无向图，要他计算所有点两两之间的最短路。

作为一个工具人，小 $A$ 熟练掌握着 $floyd$ 算法，设 $w[i][j]$ 为原图中 $(i,j)$ 之间的权值最小的边的权值，若没有边则 $w[i][j]=$无穷大。特别地，若 $i=j$，则 $w[i][j]=0$。

$Floyd$ 的 C++ 实现如下：

for(int k=1;k<=p;k++)   
for(int i=1;i<=n;i++)   
for(int j=1;j<=n;j++)   
  w[i][j]=min(w[i][j],w[i][k]+w[k][j]);   

当 $p=n$ 时，该代码就是我们所熟知的 $floyd$，然而小 $A$ 为了让代码跑的更快点，所以想减少 $p$ 的值。

令 $Di,j$ 为最小的非负整数 $x$，满足当 $p=x$ 时，点 $i$ 与点 $j$ 之间的最短路被正确计算了。

现在你需要求 $∑ni=1∑nj=1Di$,$j$，虽然答案不会很大，但为了显得本题像个计数题，你还是需要将答案对 $998244353$ 取模后输出。

输入格式

第一行一个正整数 $T$ 表示数据组数

对于每组数据：

第一行两个正整数 $n,m$，表示点数和边数。

接下来 $m$ 行，每行三个正整数 $u$,$v$,$w$ 描述一条边权为 $w$ 的边 $(u,v)$

输出格式

输出 $T$ 行，第 $i$ 行一个非负整数表示第 $i$ 组数据的答案

样例

样例输入

1
4 4
1 2 1
2 3 1
3 4 1
4 1 1   

样例输出

6

数据范围与提示

对于 $30\%$ 的数据，$ 1 \leq T \leq 30，1 \leq n \leq 300, 1 \leq m \leq 2000， 1 \leq u \leq 10 ^ 9$ 。
对于 $50\%$ 的数据，$ 1 \leq T \leq 30，1 \leq n \leq 500, 1 \leq m \leq 2000， 1 \leq u \leq 10 ^ 9$ 。
对于 $100\%$ 的数据，$ 1 \leq T \leq 30，1 \leq n \leq 1000, 1 \leq m \leq 2000， 1 \leq u \leq 10 ^ 9$ 。