21075번 - 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: the ones that have a Hamiltonian cycle. Therefore, Rikka constructs a graph based on $G$ that is surely Hamiltonian. She does so by inserting $n$ extra edges: the $i$-th 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 the $i$-th and the $j$-th vertices. Rikka wants you to calculate $$\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^{n} c (i, j)\text{.}$$

Given a graph $G_0 = \langle V, E \rangle$, a set of edges $C \subseteq E$ is a cut between vertices $i$ and $j$ if and only if in graph $G_1 = \langle V, E \setminus C \rangle$, vertices $i$ and $j$ are not (indirectly or directly) connected. The minimal cut between $i$ and $j$ is the cut with the minimal sum of edge weights. The value $c (i, j)$ of the minimal cut is this minimal sum itself.

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

Then $m$ lines follow. Each of them contains three integers $u_i$, $v_i$, and $w_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$ and $1 \leq w_i \leq 10\,000$).

Note that the graph has no self-loops, but may contain multiple edges.

Output a single line with a single integer, the answer modulo $998\,244\,353$.