Tree Of Trees

Problem

You are given $N$ edge-weighted trees $T_1, T_2,\ldots, T_N$ having $M_1, M_2,\ldots ,M_N$ nodes respectively. You also have an array $A$ of $N-1$ positive integers.

You need to connect these $N$ trees using $N-1$ edges such that each of these edges have weights equal to $A_i$ for some $i \in [1,N-1]$ and each of the $A_i$ must be used exactly once. Note that after connecting these edges, a single large tree $T$ will form consisting of $(M_1+M_2+\ldots+M_N)$ nodes. Find the minimum possible sum of distances between each pair of nodes in the final tree $T$.

Since this value can be large, output the value mod $998244353$.

Input Format

• The first line of input will contain a single integer $N$, denoting the number of trees.
• Then, you are given the $N$ trees. The description of each tree is as follows:
  • The first line contains the integer $M_i$ $(1 \le i \le N)$, the number of nodes in $i$-th tree.
  • The next $M_i-1$ lines describe the edges of the $i$-th tree. The $j$-th of these $M_i-1$ lines contains $3$ space-separated integers $u_{ij}, v_{ij}$ and $w_{ij}$, describing that there is an edge of weight $w_{ij}$ connecting the nodes $u_{ij}$ and $v_{ij}$ in tree $T_i$.
• The final line contains $N-1$ space-separated integers, $A_1, A_2,\ldots,A_{N-1}$.

Output Format

For each test case, output on a new line the minimum sum of distances between each pair of nodes in tree $T$, modulo $998244353$.

Sample Input

Input

Output

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

1

72