Problem Background

  “If Tian Yi becomes a volunteer, she might be exhausted to death.”

  “Where on earth is Class 3, Grade 7...”, the gray-haired girl complained breathlessly, refusing to believe in the absurdity. Her hair, wet with sweat, lazily clung to her fair neck, the sticky sensation faintly sketching the heat in her heart. Dozens of textbooks pressed against her chest, her hands straining under the weight as she supported her outstretched legs, moving step by step up the long staircase, gripping the railing.

  Behind her, a cute tuft of brown hair bounced along, “So~need any help?”

Problem Description

The teaching building of Magic City Middle School is represented as a tree with $n$ nodes, where node $i$ corresponds to classroom $i$ with $a_i$ students. The undirected edge $i$ is described as $(u_i, v_i, b_i)$, connecting classroom $u_i$ and $v_i$ with a vertical height difference of $b_i$ meters.

At the beginning of the new semester, textbooks need to be distributed to students, but the malfunction of the delivery system has scattered the textbooks across various classrooms. When Tian Yi is in classroom $u$, she randomly picks up $a_v$ textbooks belonging to classroom $v$ (where $v \in [1, n]$) and delivers these textbooks along the unique simple path connecting classrooms $u$ and $v$. Let the height differences of the steps Tian Yi traverses be $b_1, b_2, \cdots, b_m$ meters, and each textbook weighs 1 Newton. Then, the absolute value of the work done by Tian Yi's lifting force (positive work for going up stairs, negative work for going down stairs) is $W = a_v \left( \sum_{i=1}^{m} b_i \right)$ Joules. In other words, the cost of a delivery is the product of the terminal node's weight and the sum of the edge weights along the path.

Initially, Tian Yi is in classroom 1, but she doesn't know the way, so A Ling will guide her to deliver the textbooks, ensuring that Tian Yi visits each classroom at least once. What is the expected sum of the absolute values of the work done by Tian Yi's lifting force before achieving this goal in Joules?

Since the answer may be a decimal, to avoid precision loss, please output the answer modulo $998244353$.

Simplified Problem Statement

Given an undirected tree with $n$ nodes, each with a node weight and edge weights. Starting from position $s$ (initially $s = 1$), randomly select a target node $t$ from the $n$ nodes, incurring a cost equal to the product of the sum of edge weights on the simple path from $s$ to $t$ and the node weight of $t$, marking (can be repeated) node $t$ and setting $s$ to $t$. Find the expected sum of costs until each node is marked at least once (with node 1 initially marked). Output the answer modulo $998244353$.

Input Format

The first line contains an integer $n$, as described in the problem.

The second line contains $n$ integers, representing the number of students in each classroom.

The next $n-1$ lines each contain three integers $u_i, v_i, b_i$, indicating a staircase connecting classroom $u_i$ and $v_i$ with a height difference of $b_i$ meters.

Output Format

A single integer representing the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

3
1 2 3
1 2 1
2 3 1

Sample Output #1

332748127

Sample Input #2

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

Sample Output #2

615584181

Sample Input #3

2
1 2
1 2 2

Sample Output #3

4

Notes/Hints

Data Size and Constraints

This problem uses subtask testing.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le a_i, b_i < 998244353$, $1 \le u_i, v_i \le n$, and $u_i \ne v_i$.

见题面 Input 部分

见题面 Output 部分