Hoy Rikka recibió un grafo no dirigido $G$ con $n$ vértices y $m$ aristas. Los vértices están numerados con enteros del $1$ al $n$. La $i$-ésima arista conecta los vértices $u_i$ y $v_i$, y su peso es $w_i$.

A Rikka le gustan los grafos hamiltonianos: aquellos que tienen un ciclo hamiltoniano. Por lo tanto, Rikka construye un grafo basado en $G$ que es ciertamente hamiltoniano. Lo hace insertando $n$ aristas adicionales: la $i$-ésima arista conecta los vértices $i$ y $(i \pmod n + 1)$, y su peso es $10^9$.

Sea $c(i, j)$ el valor del corte mínimo entre el $i$-ésimo y el $j$-ésimo vértice. Rikka quiere que calcules $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j).$$

Dado un grafo $G_0 = \langle V, E \rangle$, un conjunto de aristas $C \subseteq E$ es un corte entre los vértices $i$ y $j$ si y solo si en el grafo $G_1 = \langle V, E \setminus C \rangle$, los vértices $i$ y $j$ no están conectados (directa o indirectamente). El corte mínimo entre $i$ y $j$ es el corte con la suma mínima de pesos de aristas. El valor $c(i, j)$ del corte mínimo es esta suma mínima.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$).

Luego siguen $m$ líneas. Cada una de ellas contiene tres enteros $u_i$, $v_i$ y $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$ y $1 \le w_i \le 10\,000$).

Ten en cuenta que el grafo no tiene bucles, pero puede contener aristas múltiples.

Salida

Imprime una sola línea con un único entero, la respuesta módulo $998\,244\,353$.

Ejemplos

Entrada 1

4 2
1 3 2
2 4 2

Salida 1

21067776