九条可怜想出一道图论题。

给出一张 $n$ 个点 $m$ 条边的无自环的无向图 $G$，其中第 $i$ 条边连接着 $(u_i,v_i)$，边权为 $w_i(1 \leq w_i \leq 10^4)$。

在 $G$ 的基础上，可怜构造了一张新图 $G'$，其中 $G'$ 在 $G$ 的基础上添加了 $n$ 条边，第 $i$ 条边连接 $i$ 和 $i\text{ mod }n + 1$，边权为 $10^9$。

令 $f(u,v)$ 为 $G'$ $u$ 和 $v$ 之间的最小割大小，可怜希望你计算 $\sum_{i=1}^n \sum_{j=i+1}^{n} f(i,j)$。

边集 $E$ 是 $u,v$ 之间的割当且仅当删去边集 $E$ 后 $u$ 无法到达 $v$。定义一个割的大小为割中所有边的权值和，$u,v$ 间的最小割为它们之间大小最小的割。

输入格式

第一行输入两个整数 $n,m(1 \leq n \leq 7000, 1 \leq m \leq 10^5)$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i(1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^4)$，描述了 $G$ 上的一条边。

输出格式

输出一行一个整数，表示答案。答案可能很大，你只需要输出对 $998244353$ 取模后的结果。

样例数据

样例输入

4 2
1 3 2
2 4 2

样例输出

21067776

子任务

Subtask1（19分）：$n \leq 80,m \leq 200$。

Subtask2（23分）：$n \leq 300, m \leq 1000$。

Subtask3（26分）：$n \leq 1000$。

Subtask4（32分）：无特殊限制。