無向グラフが与えられます。各頂点から他のすべての頂点への最大流を計算してください。

このグラフは特殊です。$n$ 個の点（頂点）を持つ凸多角形と、それらを結ぶいくつかの線分（辺）とみなすことができます。頂点には時計回りに $1$ から $n$ までの番号が付けられています。線分は頂点以外で交差することはありません。

各辺には容量制限があります。

$s$ から $t$ への最大流を $f(s, t)$ とします。$\left(\sum_{s=1}^{n} \sum_{t=s+1}^{n} f(s, t)\right) \pmod{998244353}$ を出力してください。

入力

最初の行には、頂点数と辺数を表す2つの整数 $n$ と $m$ が含まれます ($3 \le n \le 200000, n \le m \le 400000$)。

続く $m$ 行の各行には、辺の両端点と容量を表す3つの整数 $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行で出力してください。

入出力例

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