最短路 2

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

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

Floyd 的 C++ 实现如下：

```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$ 的值。

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

现在你需要求 $\sum_{i=1}^{n}\sum_{j=1}^{n}D_{i,j}$，虽然答案不会很大，但为了显得本题像个计数题，你还是需要将答案对 $998244353$ 取模后输出。

第一行一个正整数 $T(T\leq 30)$ 表示数据组数

对于每组数据：

第一行两个正整数 $n,m(1\leq n\leq 1000,m\leq 2000)$，表示点数和边数。

保证最多只有 $5$ 组数据满足 $max(n,m)>200$

接下来 $m$ 行，每行三个正整数 $u,v,w$ 描述一条边权为 $w$ 的边 $(u,v)$，其中 $1\leq w\leq 10^9$

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

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

6

2019 年百度之星·程序设计大赛 - 初赛三