모든 쌍 최대 유량

무방향 그래프가 주어진다. 모든 정점에서 다른 모든 정점으로 가는 최대 유량을 구하려고 한다.

이 그래프는 특별하다. $n$개의 점(정점)과 이들을 잇는 선분(간선)으로 이루어진 볼록 다각형으로 볼 수 있다. 정점은 시계 방향으로 $1$부터 $n$까지 번호가 매겨져 있다. 선분끼리는 정점에서만 서로 교차할 수 있다.

각 간선에는 용량 제한이 있다.

$s$에서 $t$로 가는 최대 유량을 $f(s,t)$라고 하자. 다음 값을 $998244353$으로 나눈 나머지를 구하라. $\left(\sum_{s=1}^n \sum_{t=s+1}^n f(s,t)\right) \bmod 998244353$

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다($3 \le n \le 200000$, $n \le m \le 400000$).

이후 $m$개의 줄에 각각 정수 $u$, $v$, $w$가 주어진다. $u$와 $v$는 간선의 양 끝점이고, $w$는 그 간선의 용량이다($1 \le u, v \le n$, $0 \le w \le 1000000000$).

중복 간선과 자기 루프는 없다.

모든 $i=1,2,\ldots,n$에 대해 정점 $i$와 정점 $(i \bmod n)+1$ 사이에 간선이 있음이 보장된다.

답을 한 줄에 출력한다.