今天 Rikka 得到了一個包含 $n$ 個頂點和 $m$ 條邊的無向圖 $G$。頂點編號為從 $1$ 到 $n$ 的整數。第 $i$ 條邊連接頂點 $u_i$ 和 $v_i$，其權重為 $w_i$。

Rikka 喜歡哈密頓圖：即那些擁有哈密頓迴路的圖。因此，Rikka 在 $G$ 的基礎上建構了一個必然是哈密頓圖的圖。她透過插入 $n$ 條額外的邊來達成：第 $i$ 條邊連接頂點 $i$ 和 $(i \pmod n + 1)$，其權重為 $10^9$。

令 $c(i, j)$ 為第 $i$ 個頂點與第 $j$ 個頂點之間的最小割值。Rikka 希望你計算： $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$$

給定一個圖 $G_0 = \langle V, E \rangle$，邊集 $C \subseteq E$ 是頂點 $i$ 和 $j$ 之間的一個割，若且唯若在圖 $G_1 = \langle V, E \setminus C \rangle$ 中，頂點 $i$ 和 $j$ 不連通（無論是直接或間接）。$i$ 和 $j$ 之間的最小割是指邊權重總和最小的割。最小割的值 $c(i, j)$ 即為該最小權重總和。

輸入格式

第一行包含兩個整數 $n$ 和 $m$ ($3 \le n \le 20\,000, 0 \le m \le 20\,000$)。

接下來 $m$ 行，每行包含三個整數 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$ 且 $1 \le w_i \le 10\,000$)。

注意，該圖沒有自環，但可能包含重邊。

輸出格式

輸出單行一個整數，即答案對 $998\,244\,353$ 取模後的結果。

範例

輸入 1

4 2
1 3 2
2 4 2

輸出 1

21067776