Background

“This task can never be completed. I will not repeat the same mistake again.”

“Having learned love and emotions, he is no longer a robot... From this point of view, 3000A is your son, Huo Xing.”

Farewell, 3000A! Detective Magic Horn

Problem Description

You are given a tree with $n$ nodes, and $m$ paths $(u, v, w)$, where $w$ can be regarded as the weight assigned to the path $(u, v)$. For a set of paths $S$, its weight $W(S)$ is defined as follows: find a subset of $S$ with the maximum possible sum of weights, such that no two paths in this subset share a common vertex. The sum of weights of all paths in this subset is $W(S)$.

Define $f(u, v) = w$ as the smallest non-negative integer $w$ such that, for the path set $U$ formed by the given $m$ paths, we have $W(U \cup \{(u, v, w + 1)\}) > W(U)$.

Compute the following expression modulo $998244353$:

Input Format

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

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

The next $m$ lines each contain three integers $u, v, w$, meaning that a path with endpoints $u, v$ and weight $w$ is added into the set.

Output Format

Output one integer, the answer.

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

100

Hint

Sample 1 Explanation

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

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 3\times 10^5$, $0 \le m \le 3\times 10^5$, and $1 \le w \le 10^9$.

Translated by ChatGPT 5