{"raw_statement":[{"iden":"statement","content":"小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。\n\nF 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。\n\n当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。\n\n我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。\n\n为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。\n\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)$。\n\n由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。\n\n**方案之间相互独立**，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。"},{"iden":"input","content":"第一行两个整数 $n,q$。\n\n接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,c_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路，其费用为 $c_i$。\n\n接下来 $q$ 行，第 $i$ 行两个整数 $k_i,w_i$，表示一个新建道路的方案。"},{"iden":"output","content":"共 $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$。"},{"iden":"note","content":"#### 【样例解释 #1】\n\n在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/j871257i.png)\n\n例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。\n\n容易求得此时 $\\sum\\limits_{i=1}^{n+1} \\sum\\limits_{j=1}^{n+1} cost(i,j)=100$。\n\n#### 【样例 #3】\n\n见附加文件中的 `city/city3.in` 与 `city/city3.ans`。\n\n该样例满足测试点 $4$ 的限制。\n\n#### 【样例 #4】\n\n见附加文件中的 `city/city4.in` 与 `city/city4.ans`。\n\n该样例满足测试点 $11$ 的限制。\n\n#### 【样例 #5】\n\n见附加文件中的 `city/city5.in` 与 `city/city5.ans`。\n\n该样例满足测试点 $14$ 的限制。\n\n#### 【样例 #6】\n\n见附加文件中的 `city/city6.in` 与 `city/city6.ans`。\n\n该样例满足测试点 $20$ 的限制。\n\n#### 【数据范围】\n\n对于 $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\n|测试点编号|$n \\le$|$q \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|\n|$1\\sim3$|$80$|$80$|无|\n|$4\\sim7$|$5000$|$5000$|无|\n|$8\\sim10$|$5000$|$2\\times10^5$|无|\n|$11\\sim13$|$2\\times10^5$|$2\\times10^5$|A|\n|$14\\sim16$|$2\\times10^5$|$2\\times10^5$|B|\n|$17\\sim20$|$2\\times10^5$|$2\\times10^5$|无|\n\n特殊性质 A：保证对于所有的 $1 \\le i \\lt n$，都有 $u_i=i,v_i=i+1$。\n\n特殊性质 B：保证对于所有的 $1 \\le i \\le q$，都有 $k_i=1$。"}],"translated_statement":null,"sample_group":[["4 2\n2 1 3\n3 2 2\n4 2 4\n1 2\n2 2","100\n88"],["9 5\n2 3 6\n6 1 4\n5 2 10\n2 4 1\n9 1 9\n2 8 3\n1 2 3\n7 4 8\n4 9\n7 3\n6 1\n9 7\n2 1\n","1050\n1054\n970\n1148\n896"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}