九条可怜想出一道图论题。
给出一张 $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分）：无特殊限制。