{"raw_statement":[{"iden":"statement","content":"You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex.\n\nThe 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.\n\nEach edge has a capacity constraint. \n\nDenote the maximum flow from $s$ to $t$ by $f (s, t)$. Output $(sum_{s = 1}^n sum_{t = s + 1}^n f (s, t)) bmod 998244353$.\n\nThe first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3 <= n <= 200000, n <= m <= 400000$).\n\nEach of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1 <= u, v <= n, 0 <= w <= 1000000000$).\n\nIt is guaranteed there are no multiple edges and self-loops.\n\nIt is guaranteed that there is an edge between vertex $i$ and vertex $(i bmod n) + 1$ for all $i = 1, 2, \\\\dots, n$.\n\nOutput the answer in one line.\n\n"},{"iden":"input","content":"The first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3 <= n <= 200000, n <= m <= 400000$).Each of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1 <= u, v <= n, 0 <= w <= 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, \\\\dots, n$."},{"iden":"output","content":"Output the answer in one line."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $, vertices labeled clockwise on a convex polygon.  \n- $ E $: a set of $ m $ edges, each $ (u, v, w) \\in E $ with capacity $ w \\in \\mathbb{Z}_{\\ge 0} $.  \n- $ \\forall i \\in \\{1, \\dots, n\\} $, edge $ (i, (i \\bmod n) + 1) \\in E $ (polygon boundary edges).  \n\nLet $ f(s, t) $ denote the maximum flow from vertex $ s $ to vertex $ t $ in $ G $, under edge capacities.\n\n**Constraints**  \n1. $ 3 \\le n \\le 200000 $  \n2. $ n \\le m \\le 400000 $  \n3. $ 0 \\le w \\le 10^9 $ for all edge capacities  \n4. No multiple edges or self-loops  \n\n**Objective**  \nCompute:  \n$$\n\\left( \\sum_{s=1}^{n} \\sum_{t=s+1}^{n} f(s, t) \\right) \\bmod 998244353\n$$","simple_statement":"You are given a convex polygon with n vertices (labeled 1 to n clockwise) and m edges (including the polygon sides). Each edge has a capacity. Compute the sum of maximum flows between all pairs of vertices (s, t) where s < t, modulo 998244353.","has_page_source":false}