今天 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