Glass Tree Scoring

You are given a tree with n nodes. Each node i has a number of glasses V_i and each edge has an associated weight W.

For any ordered pair of distinct nodes (u, v) (u ≠ v), consider the unique simple path from u to v. Let the edge sum be the sum of the weights on the path, i.e. \(\sum W_e\). Let the node sum be the sum of the glasses at all nodes on this path (including u and v), i.e. \(\sum V_i\). The score obtained by the operation on this pair is the product of these two sums:

\(\Bigl(\sum W_e\Bigr)\times\Bigl(\sum V_i\Bigr)\).

Considering all ordered pairs (u, v) with u ≠ v (note that (u,v) and (v,u) are counted separately), compute the total score mod 998244353.

inputFormat

The first line contains an integer n (the number of nodes).

The second line contains n space‐separated integers: V₁, V₂, ..., V_n, where V_i is the number of glasses at node i.

Each of the next n − 1 lines contains three integers u, v, w representing an undirected edge between node u and node v with weight w.

outputFormat

Output a single integer: the total score obtained from all operations, taken modulo 998244353.

sample

3
1 2 3
1 2 1
2 3 2

62