給定一個無向圖。你想要計算從每個頂點到其他每個頂點的最大流。

這個圖很特殊。你可以將其視為一個具有 $n$ 個點（頂點）的凸多邊形，以及連接它們的一些線段（邊）。頂點按順時針順序標記為 $1$ 到 $n$。這些線段只能在頂點處相交。

每條邊都有一個容量限制。

令 $f(s, t)$ 為從 $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