"This task can never be completed. I will not repeat the same mistake again." "Having understood love and emotion, he is no longer a robot... From this perspective, 3000A is your son, Huo Xing." —— Farewell, 3000A! Magic Eye Detective

Given a tree with $n$ nodes and $m$ paths $(u, v, w)$, where $w$ is the weight assigned to the path $(u, v)$. The weight $W(S)$ of a set of paths $S$ is defined as: find a subset of $S$ with the maximum total weight such that no two paths in the subset share any common vertices. The sum of the weights of the paths in this subset is $W(S)$.

Let $f(u, v) = w$ be the smallest non-negative integer $w$ such that for a given set of paths $U$, $W(U \cup \{(u, v, w + 1)\}) > W(U)$.

Calculate the following sum modulo $998244353$:

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

Input

The first line contains two integers $n$ and $m$, representing the number of nodes in the tree and the number of given paths, respectively.

The next $n-1$ lines each contain two integers $u, v$, representing an edge in the tree.

The next $m$ lines each contain three integers $u, v, w$, representing a path between endpoints $u$ and $v$ with weight $w$ added to the set.

Output

Output a single integer representing the answer.

Examples

Input 1

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

Output 1

100

Note 1

$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$

Subtasks

For $100\%$ of the data, $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$.