Expected Cost of Textbook Distribution

In a school in the magic city, the teaching building is structured as a tree with \(n\) nodes. Each node \(i\) represents a classroom with a weight \(a_i\) (the number of textbooks originally in that classroom). The tree has \(n-1\) undirected edges; each edge is given by \((u_i,v_i,b_i)\) and represents a staircase between classrooms \(u_i\) and \(v_i\) with a vertical height difference of \(b_i\) meters.

Due to a fault in the transmission system on the first day of the new term, textbooks are scattered in all classrooms. Initially, the messenger (Tianyi) is at classroom \(1\) (which is considered visited). For every subsequent transport, a target classroom \(t\) is selected uniformly at random from \([1,n]\); the messenger picks up all \(a_t\) textbooks from classroom \(t\) and carries them from the current classroom \(s\) to \(t\) along the unique simple path. If the edges along the path have weights \(b_1, b_2, \dots, b_m\) (in meters) and each textbook has weight \(1\text{N}\), then the absolute work done by Tianyi is \[ W = a_t\left(\sum_{i=1}^{m} b_i\right)\text{J}. \] That is, the cost of each transportation is defined as the product of the endpoint's weight (\(a_t\)) and the sum of the edge weights on the path from \(s\) to \(t\).

Accompanied by her friend A Ling, Tianyi must eventually visit every classroom at least once (classroom \(1\) is visited initially) while transporting textbooks. Compute the expected total cost (i.e. the expected sum of the absolute work done in each transportation step) before all classrooms are visited. Since the answer might not be an integer, output it modulo \(998244353\). All formulas above should be interpreted in \(\LaTeX\) format.

Simplified Problem Statement

You are given a tree with \(n\) nodes where each node \(i\) has a weight \(a_i\) and each edge has a weight \(b\). Starting at node \(1\) (which is initially marked as visited), you repeatedly perform the following process:

• Randomly choose a target node \(t\) from \(1\) to \(n\) (each uniformly with probability \(\frac{1}{n}\)).
• Pay a cost equal to the distance from the current node \(s\) to \(t\) (the sum of edge weights along the unique simple path) multiplied by \(a_t\).
• Mark node \(t\) (re‐marking is allowed) and update \(s\) to \(t\).

The process stops as soon as every node has been marked at least once. Find the expected total cost incurred during this process, modulo \(998244353\).

inputFormat

The input begins with an integer \(n\) \((1 \le n \le 10)\) — the number of nodes in the tree (note: the constraint is small for this problem). The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) — the weight (number of textbooks) at each node.

Each of the next \(n-1\) lines contains three integers \(u, v, b\) \((1 \le u,v \le n, 1 \le b \le 10^9)\) meaning that there is an undirected edge between nodes \(u\) and \(v\) with weight \(b\) (the vertical height difference in meters).

outputFormat

Output a single integer — the expected total cost of all transportation steps modulo \(998244353\).

sample

2
1 2
1 2 3

6