Aujourd'hui, Rikka a reçu un graphe non orienté $G$ avec $n$ sommets et $m$ arêtes. Les sommets sont numérotés par des entiers de $1$ à $n$. La $i$-ème arête relie les sommets $u_i$ et $v_i$, et son poids est $w_i$.

Rikka aime les graphes hamiltoniens : ceux qui possèdent un cycle hamiltonien. Par conséquent, Rikka construit un graphe basé sur $G$ qui est assurément hamiltonien. Elle le fait en insérant $n$ arêtes supplémentaires : la $i$-ème arête relie les sommets $i$ et $(i \pmod n + 1)$, et son poids est $10^9$.

Soit $c(i, j)$ la valeur de la coupe minimale entre le $i$-ème et le $j$-ème sommet. Rikka veut que vous calculiez :

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j)$$

Étant donné un graphe $G_0 = \langle V, E \rangle$, un ensemble d'arêtes $C \subseteq E$ est une coupe entre les sommets $i$ et $j$ si et seulement si dans le graphe $G_1 = \langle V, E \setminus C \rangle$, les sommets $i$ et $j$ ne sont pas connectés (directement ou indirectement). La coupe minimale entre $i$ et $j$ est la coupe ayant la somme des poids des arêtes minimale. La valeur $c(i, j)$ de la coupe minimale est cette somme minimale elle-même.

Entrée

La première ligne contient deux entiers $n$ et $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$).

Ensuite, $m$ lignes suivent. Chacune d'elles contient trois entiers $u_i$, $v_i$ et $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$ et $1 \le w_i \le 10\,000$).

Notez que le graphe ne contient pas de boucles, mais peut contenir des arêtes multiples.

Sortie

Affichez une seule ligne avec un seul entier, la réponse modulo $998\,244\,353$.

Exemples

Entrée 1

4 2
1 3 2
2 4 2

Sortie 1

21067776