Dany jest graf nieskierowany. Chcesz obliczyć maksymalny przepływ z każdego wierzchołka do każdego innego wierzchołka.

Graf jest szczególny. Można go traktować jako wielokąt wypukły o $n$ punktach (wierzchołkach) oraz pewnych odcinkach (krawędziach) łączących je. Wierzchołki są ponumerowane od $1$ do $n$ zgodnie z ruchem wskazówek zegara. Odcinki mogą przecinać się tylko w wierzchołkach.

Każda krawędź posiada ograniczenie przepustowości.

Oznaczmy maksymalny przepływ z $s$ do $t$ jako $f(s, t)$. Wypisz $\left(\sum_{s=1}^{n} \sum_{t=s+1}^{n} f(s, t)\right) \pmod{998244353}$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$, reprezentujące liczbę wierzchołków i krawędzi ($3 \le n \le 200000$, $n \le m \le 400000$).

Każda z kolejnych $m$ linii zawiera trzy liczby całkowite $u, v, w$ oznaczające dwa końce krawędzi oraz jej przepustowość ($1 \le u, v \le n$, $0 \le w \le 1000000000$).

Gwarantuje się, że nie ma krawędzi wielokrotnych ani pętli własnych.

Gwarantuje się, że istnieje krawędź między wierzchołkiem $i$ a wierzchołkiem $(i \pmod n) + 1$ dla wszystkich $i = 1, 2, \dots, n$.

Wyjście

Wypisz odpowiedź w jednej linii.

Przykład

Wejście 1

6 8
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 1 100000
1 4 1000000
1 5 10000000

Wyjście 1

12343461