「MXOI Round 1」城市

小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。 F 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。 当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。 我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。 为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。 他共有 $q$ 个新建道路的方案，每个方案会给定两个参数 $k_i,w_i$；对于每一个方案，你需要求出在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$。 由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。 **方案之间相互独立**，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。

第一行两个整数 $n,q$。 接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,c_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路，其费用为 $c_i$。 接下来 $q$ 行，第 $i$ 行两个整数 $k_i,w_i$，表示一个新建道路的方案。

共 $q$ 行，每行一个整数，第 $i$ 行的整数表示在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和对 $998244353$ 取模的结果，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$。

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

100
88

9 5
2 3 6
6 1 4
5 2 10
2 4 1
9 1 9
2 8 3
1 2 3
7 4 8
4 9
7 3
6 1
9 7
2 1

1050
1054
970
1148
896

#### 【样例解释 #1】 在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：  例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。 容易求得此时 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$。 #### 【样例 #3】 见附加文件中的 `city/city3.in` 与 `city/city3.ans`。 该样例满足测试点 $4$ 的限制。 #### 【样例 #4】 见附加文件中的 `city/city4.in` 与 `city/city4.ans`。 该样例满足测试点 $11$ 的限制。 #### 【样例 #5】 见附加文件中的 `city/city5.in` 与 `city/city5.ans`。 该样例满足测试点 $14$ 的限制。 #### 【样例 #6】 见附加文件中的 `city/city6.in` 与 `city/city6.ans`。 该样例满足测试点 $20$ 的限制。 #### 【数据范围】 对于 $100\%$ 的数据，$2 \le n \le 2\times10^5$，$1 \le q \le 2\times10^5$，$1 \le u_i,v_i,k_i \le n$，$1 \le c_i,w_i \le 10^6$，保证从任意一个城市出发，都能通过原本存在的 $n-1$ 条双向道路，到达任意一个城市。 |测试点编号|$n \le$|$q \le$|特殊性质| |:---:|:---:|:---:|:---:| |$1\sim3$|$80$|$80$|无| |$4\sim7$|$5000$|$5000$|无| |$8\sim10$|$5000$|$2\times10^5$|无| |$11\sim13$|$2\times10^5$|$2\times10^5$|A| |$14\sim16$|$2\times10^5$|$2\times10^5$|B| |$17\sim20$|$2\times10^5$|$2\times10^5$|无| 特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $u_i=i,v_i=i+1$。 特殊性质 B：保证对于所有的 $1 \le i \le q$，都有 $k_i=1$。