최소 컷

오늘 Rikka는 정점이 $n$개, 간선이 $m$개인 무방향 그래프 $G$를 얻었다. 정점은 1부터 $n$까지의 정수로 번호가 매겨져 있다. $i$번째 간선은 정점 $u_i$와 $v_i$를 잇고, 가중치는 $w_i$이다.

Rikka는 해밀턴 그래프, 즉 해밀턴 순환을 갖는 그래프를 좋아한다. 그래서 Rikka는 $G$를 바탕으로 항상 해밀턴 그래프가 되는 그래프를 만든다. 이를 위해 $n$개의 간선을 추가한다. $i$번째 추가 간선은 정점 $i$와 $(i \bmod n + 1)$을 잇고, 가중치는 $10^9$이다.

$c(i, j)$를 정점 $i$와 $j$ 사이 최소 컷의 값이라고 하자. 간선 집합 $C \subseteq E$가 $i$와 $j$ 사이의 컷이라는 것은, 그래프 $G_1 = \langle V, E \setminus C \rangle$에서 두 정점 $i$와 $j$가 직접 또는 간접으로 연결되지 않는다는 뜻이다. 최소 컷은 간선 가중치 합이 가장 작은 컷이며, $c(i, j)$는 그 합이다.

Rikka는 다음 값을 구해 달라고 한다. $\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($3 \leq n \leq 20000$, $0 \leq m \leq 20000$).

이어서 $m$개의 줄에 세 정수 $u_i$, $v_i$, $w_i$가 주어진다 ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq w_i \leq 10000$).

그래프에는 자기 루프가 없지만 중복 간선은 있을 수 있다.

답을 998244353으로 나눈 나머지를 한 줄에 출력한다.