Minimal Cut

Today Rikka got an undirected graph $G$ with $n$ vertices and $m$ edges. The vertices are numbered by integers from $1$ to $n$. The $i$-th edge connects vertices $u_i$ and $v_i$, and its weight is $w_i$.

Rikka likes Hamiltonian graphs, that is, graphs that have a Hamiltonian cycle. So Rikka builds a graph from $G$ that is always Hamiltonian. She does this by adding $n$ extra edges. The $i$-th extra edge connects vertices $i$ and $(i \bmod n + 1)$, and its weight is $10^9$.

Let $c(i, j)$ be the value of the minimal cut between vertices $i$ and $j$. A set of edges $C \subseteq E$ is a cut between $i$ and $j$ if, in the graph $G_1 = \langle V, E \setminus C \rangle$, vertices $i$ and $j$ are not connected, directly or indirectly. The minimal cut is the cut with the smallest total edge weight, and $c(i, j)$ is that total.

Rikka asks you to compute the following sum. $\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$

The first line contains two integers $n$ and $m$ ($3 \leq n \leq 20000$, $0 \leq m \leq 20000$).

Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $w_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq w_i \leq 10000$).

The graph has no self-loops, but it may contain multiple edges.

Print a single line containing the answer modulo $998244353$.