小 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 取模后的结果。

对于该图：

• D_{1,2} = 1（直接边）
• D_{1,3} = 2（最短路 1 \to 2 \to 3，中间点最大编号为 2）
• D_{1,4} = 3（最短路 1 \to 2 \to 3 \to 4，中间点最大编号为 3）
• D_{2,3} = 2（直接边）
• D_{2,4} = 3（经过点 3）
• D_{3,4} = 3（直接边）

对称点对同理，总和为 16。

• 1 \le n \le 500
• 1 \le m \le \frac{n(n-1)}{2}
• 1 \le w \le 10^9
• 保证图连通且无重边