Rikka otrzymała nieskierowany graf $G$ o $n$ wierzchołkach i $m$ krawędziach. Wierzchołki są ponumerowane liczbami całkowitymi od $1$ do $n$. $i$-ta krawędź łączy wierzchołki $u_i$ oraz $v_i$ i ma wagę $w_i$.

Rikka lubi grafy hamiltonowskie: takie, które posiadają cykl Hamiltona. Dlatego Rikka konstruuje graf oparty na $G$, który z pewnością jest hamiltonowski. Robi to poprzez dodanie $n$ dodatkowych krawędzi: $i$-ta krawędź łączy wierzchołki $i$ oraz $(i \pmod n + 1)$ i ma wagę $10^9$.

Niech $c(i, j)$ oznacza wartość minimalnego przekroju między wierzchołkiem $i$ a wierzchołkiem $j$. Rikka chce, abyś obliczył: $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$$

Dla grafu $G_0 = \langle V, E \rangle$, zbiór krawędzi $C \subseteq E$ jest przekrojem między wierzchołkami $i$ oraz $j$ wtedy i tylko wtedy, gdy w grafie $G_1 = \langle V, E \setminus C \rangle$ wierzchołki $i$ oraz $j$ nie są połączone (bezpośrednio ani pośrednio). Minimalny przekrój między $i$ oraz $j$ to przekrój o minimalnej sumie wag krawędzi. Wartość $c(i, j)$ minimalnego przekroju to właśnie ta minimalna suma.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$).

Następnie następuje $m$ linii. Każda z nich zawiera trzy liczby całkowite $u_i$, $v_i$ oraz $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$ oraz $1 \le w_i \le 10\,000$).

Zauważ, że graf nie posiada pętli własnych, ale może zawierać krawędzie wielokrotne.

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą, wynik modulo $998\,244\,353$.

Przykład

Wejście 1

4 2
1 3 2
2 4 2

Wyjście 1

21067776