K. All Pair Maximum Flow
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Output the answer in one line.

Example
Input
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
Output
12343461