Description

You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex.

The graph is special. You can regard it as a convex polygon with $n$ points (vertices) and some line segments (edges) connecting them. The vertices are labeled from $1$ to $n$ in the clockwise order. The line segments can only intersect each other at the vertices.

Each edge has a capacity constraint.

Denote the maximum flow from $s$ to $t$ by $f(s,t)$. Output $\left(\sum_{s=1}^n \sum_{t=s+1}^n f(s,t) \right) \bmod 998244353$.

Input Format

The first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3\le n\le 200000, n\le m\le 400000$).

Each of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1\le u, v\le n, 0\le w\le 1000000000$).

It is guaranteed there are no multiple edges and self-loops.

It is guaranteed that there is an edge between vertex $i$ and vertex $(i\bmod n)+1$ for all $i=1,2,\ldots, n$.

Output Format

Output the answer in one line.

6 8
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 1 100000
1 4 1000000
1 5 10000000

12343461