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$ です。

頂点 $i$ と頂点 $j$ の間の最小カットの値を $c(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)$ は、その最小の総和そのものです。

入力

最初の行には2つの整数 $n$ と $m$ ($3 \le n \le 20\,000, 0 \le m \le 20\,000$) が含まれます。

続く $m$ 行には、それぞれ3つの整数 $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行で出力してください。

入出力例

入力 1

4 2
1 3 2
2 4 2

出力 1

21067776