Вам дан неориентированный граф. Вам необходимо вычислить максимальный поток из каждой вершины в любую другую вершину.

Граф обладает особыми свойствами. Его можно представить как выпуклый многоугольник с $n$ точками (вершинами) и некоторыми отрезками (ребрами), соединяющими их. Вершины пронумерованы от $1$ до $n$ по часовой стрелке. Отрезки могут пересекаться друг с другом только в вершинах.

Каждое ребро имеет ограничение по пропускной способности.

Обозначим максимальный поток из $s$ в $t$ как $f(s, t)$. Выведите $\left(\sum_{s=1}^{n} \sum_{t=s+1}^{n} f(s, t)\right) \pmod{998244353}$.

Входные данные

Первая строка содержит два целых числа $n$ и $m$, представляющих количество вершин и ребер ($3 \le n \le 200000$, $n \le m \le 400000$).

Каждая из следующих $m$ строк содержит три целых числа $u, v, w$, обозначающих два конца ребра и его пропускную способность ($1 \le u, v \le n$, $0 \le w \le 1000000000$).

Гарантируется отсутствие кратных ребер и петель.

Гарантируется, что существует ребро между вершиной $i$ и вершиной $(i \pmod n) + 1$ для всех $i = 1, 2, \dots, n$.

Выходные данные

Выведите ответ одной строкой.

Примеры

Входные данные 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

Выходные данные 1

12343461