«Эта задача никогда не будет решена. Я больше не совершу ту же ошибку».

«Познав любовь и чувства, он перестал быть роботом... С этой точки зрения, 3000A — твой сын, Хо Син».

— Прощай, 3000A! «Детектив из магического уголка»

Дано дерево с $n$ вершинами и $m$ путей $(u, v, w)$, где $w$ — вес пути. Для множества путей $S$ его вес $W(S)$ определяется как максимальная суммарная стоимость подмножества путей из $S$, в котором любые два пути не имеют общих вершин.

Пусть $f(u, v) = w$ — минимальное неотрицательное целое число $w$ такое, что для заданного множества $U$ из $m$ путей выполняется условие $W(U \cup \{(u, v, w + 1)\}) > W(U)$.

Вычислите значение следующего выражения по модулю $998244353$:

$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$

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

Первая строка содержит два целых числа $n$ и $m$, количество узлов в дереве и количество заданных путей соответственно.

Следующие $n-1$ строк содержат по два целых числа $u, v$, описывающих ребро дерева.

Следующие $m$ строк содержат по три целых числа $u, v, w$, описывающих путь между узлами $u$ и $v$ с весом $w$.

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

Выведите одно целое число — ответ на задачу.

Примеры

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

4 4
1 2
1 3
1 4
1 2 1
3 3 2
1 4 3
2 4 6

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

100

Примечание

$f(1, 1) = 6, f(1, 2) = 6, f(1, 3) = 8, f(1, 4) = 6$

$f(2, 1) = 6, f(2, 2) = 3, f(2, 3) = 8, f(2, 4) = 6$

$f(3, 1) = 8, f(3, 2) = 8, f(3, 3) = 2, f(3, 4) = 8$

$f(4, 1) = 6, f(4, 2) = 6, f(4, 3) = 8, f(4, 4) = 5$

Подзадачи

Для $100\%$ данных гарантируется, что $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$.