Сегодня Рикка получила неориентированный граф $G$ с $n$ вершинами и $m$ ребрами. Вершины пронумерованы целыми числами от $1$ до $n$. $i$-е ребро соединяет вершины $u_i$ и $v_i$, а его вес равен $w_i$.

Рикка любит гамильтоновы графы: те, в которых есть гамильтонов цикл. Поэтому Рикка строит граф на основе $G$, который гарантированно является гамильтоновым. Она делает это, добавляя $n$ дополнительных ребер: $i$-е ребро соединяет вершины $i$ и $(i \pmod n + 1)$, а его вес равен $10^9$.

Пусть $c(i, j)$ — значение минимального разреза между $i$-й и $j$-й вершинами. Рикка хочет, чтобы вы вычислили $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} c(i, j).$$

Для графа $G_0 = \langle V, E \rangle$ множество ребер $C \subseteq E$ является разрезом между вершинами $i$ и $j$ тогда и только тогда, когда в графе $G_1 = \langle V, E \setminus C \rangle$ вершины $i$ и $j$ не соединены (ни косвенно, ни напрямую). Минимальный разрез между $i$ и $j$ — это разрез с минимальной суммой весов ребер. Значение $c(i, j)$ минимального разреза — это сама эта минимальная сумма.

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

Первая строка содержит два целых числа $n$ и $m$ ($3 \le n \le 20\,000$, $0 \le m \le 20\,000$).

Затем следуют $m$ строк. Каждая из них содержит три целых числа $u_i$, $v_i$ и $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$ и $1 \le w_i \le 10\,000$).

Заметьте, что в графе нет петель, но могут быть кратные ребра.

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

Выведите одну строку с единственным целым числом — ответом по модулю $998\,244\,353$.

Примеры

Пример 1

4 2
1 3 2
2 4 2

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

21067776