给定一个无向图，你需要计算从每个顶点到其他所有顶点的最大流。

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

每条边都有一个容量限制。

记从 $s$ 到 $t$ 的最大流为 $f(s, t)$。输出 $\left(\sum_{s=1}^{n} \sum_{t=s+1}^{n} f(s, t)\right) \pmod{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, \dots, n$，顶点 $i$ 和顶点 $(i \pmod n) + 1$ 之间都存在一条边。

输出格式

输出一行答案。

样例

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

输出 1

12343461