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

作为一个工具人，小 A 熟练掌握着 Floyd 算法。设 w[i][j] 为原图中 (i,j) 之间权值最小的边的权值，若没有边则 w[i][j] = \infty。特别地，若 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 的值。

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

现在你需要求：

\sum_{i=1}^{n}

\sum_{j=1}^{n}

D_{i,j}

虽然答案不会很大，但为了显得本题像个计数题，你还是需要将答案对 998244353 取模后输出。

第一行包含两个整数 n 和 m，分别表示点数和边数。

接下来 m 行，每行包含三个整数 u, v, w，表示一条连接 u 和 v 的无向边，边权为 w。

输出一个整数，表示 \sum_{i=1}^{n}

\sum_{j=1}^{n}

D_{i,j} 对 998244353 取模后的结果。

数据范围

• 1 \le n \le 1000
• m \le 2000
• T \le 30
• 最多只有 5 组数据满足 \max(n, m) > 200

百度之星