题目背景

  “如果天依来当志愿者的话，说不定会被累死哟。”

---

  “七年三班又在什么鬼地方啊……”，不信这个邪的小灰毛喘息着抱怨。发丝凝着汗珠，慵懒地趴在白皙的后颈，粘黏感若有若无地在心里描画着燥热。数十本教材抵在胸口，大腿前伸直的双手托着艰难的重量，贴着扶手一步一步挪上漫长的台阶。

  背后，一撮可爱的棕色呆毛蹦蹦跳跳地跟了上来，“所以~需要帮忙吗？”

题目描述

魔都中学的教学楼是一棵有 $n$ 个结点的树，结点 $i$ 对应编号为 $i$，人数为 $a_i$ 的教室。无向边 $i$ 描述为 $(u_i,v_i,b_i)$，对应连接教室 $u_i$ 和 $v_i$，垂直高差为 $b_i\ \text{m}$ 的台阶。

新学期开学，需要为同学们分发教材，不过传送系统的故障导致教材散落在各个教室。当天依在教室 $u$ 时，会随机抱起属于教室 $v~(v\in[1,n])$ 的 $a_v$ 本教材，并沿连接教室 $u,v$ 的唯一简单路径将这些教材送到教室 $v$。设天依走过的台阶高差为 $b_1,b_2,\cdots,b_m\ \text{m}$，每本教材重力为 $1\text{N}$，那么称此次运送中，天依的托举力做功的绝对值（上台阶取正功，下台阶取负功的绝对值）为 $W=a_v\left( \sum_{i=1}^{m} b_i \right)\text{J}$。换句话来说，一次运送的代价是终点点权与走过路径边权之和的乘积。

初始时，天依在 $1$ 号教室，但她不认识路，所以阿绫会带着天依运送教材，使得天依到达过每个教室至少一次。那么在达到这一目标之前，天依托举力做功的绝对值之和的期望为多少 $\text{J}$？

由于答案可能是一个小数，为了避免损失精度，请输出答案在 $998244353$ 模意义下的值。

---

简化题意

给定一棵包含 $n$ 个点，有点权和边权的无根树。设当前位置 $s$（初始时 $s=1$），每次在 $n$ 个结点内随机选择目标结点 $t$，付出「$s$ 到 $t$ 的简单路径上的边权之和」$\times$「$t$ 的点权」的代价，标记（可以重复标记）点 $t$ 并把 $s$ 置为 $t$。求每个点至少被标记一次时（其中 $1$ 号结点一开始就被标记）代价之和的期望。答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$，含义如题所述。

第二行有 $n$ 个整数，表示每个教室的人数。

随后 $n-1$ 行，每行三个整数 $u_i,v_i,b_i$ 表示教室 $u_i$ 与教室 $v_i$ 之间有一垂直高差为 $b_i\ \text{m}$ 的台阶。

输出格式

一行一个整数，表示答案在 $998244353$ 模意义下的值。

3
1 2 3
1 2 1
2 3 1

332748127

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

615584181

2
1 2
1 2 2

4

提示

---

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le a_i,b_i\lt 998244353$，$1\le u_i,v_i\le n$，保证 $u_i\ne v_i$。

子任务	分值	$n$	特殊限制
1	5	$\le 3$	/
2	10	$\le 13$
3		$\le 20$
4	25	$\le 5\times 10^3$
5		/	对于 $\forall 1\le i\le n$，$a_i=1$
6	10		对于每一条边，$v_i=u_i+1$，即树是一条链。
7	35		/