406656: GYM102471 K All Pair Maximum Flow

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$$$.

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 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