题目描述

给定一个无向图。你需要计算每一对顶点之间的最大流。

该图具有特殊结构。你可以将其视为一个有 $n$ 个点（顶点）的凸多边形，并有若干线段（边）连接这些顶点。顶点按顺时针顺序从 $1$ 到 $n$ 编号。线段只能在顶点处相交。

每条边都有容量限制。

记从 $s$ 到 $t$ 的最大流为 $f(s,t)$。请输出 $\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$，表示一条边的两个端点和容量（$1\le u, v\le n, 0\le w\le 1000000000$）。

保证没有重边和自环。

保证对于所有 $i=1,2,\ldots, n$，顶点 $i$ 和顶点 $(i\bmod n)+1$ 之间存在一条边。

输出格式

输出一行一个整数，表示答案。

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

提示

由 ChatGPT 4.1 翻译