Description

First, a tree is given. Each node has $V_i$ pieces of glass, and each edge has a weight $W_i$.

In each operation, Xiao S can choose two nodes $u, v (u \ne v)$. On the unique path from node $u$ to node $v$, the edge sum is the sum of the weights of all edges on the path, i.e. $\sum W_i$. The node sum is the sum of the numbers of glass on all nodes on the path (including $u, v$), i.e. $\sum V_i$. Xiao S can obtain a score equal to the product of the edge sum and the node sum, i.e. $\sum W_i \times \sum V_i$.

Any two operations cannot be exactly the same, and $(u, v)$ and $(v, u)$ are considered two different operations.

However, sometimes the tree is too large, and Xiao S needs your help. He wants you to tell him: after $N(N-1)$ operations, how many points can be obtained in total. The result may be very large; you only need to output the answer modulo $998244353$.

Input Format

The first line contains an integer $N$, denoting the number of nodes in the tree.
The second line contains $N$ integers, where the $i$-th number $V_i$ denotes the number of glass at node $i$.
The next $N-1$ lines each contain three numbers $x, y, z$, indicating that there is a tree edge between nodes $x$ and $y$ with weight $z$.

Output Format

Output one integer, the total score modulo $998244353$.

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

256

Hint

Sample Explanation

For sample $1$, the tree looks like this:

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $0 \le V_i, W_i \lt 2^{16}$ and $1 \le N \le 2 \times 10^6$.

Notes

Minecraft OI Round 2 D

• Maker: Inf_Voltage
• Tester: tarjin

Translated by ChatGPT 5