Problem Description

Little C is the president of Country F. Although this country exists only in an online game, he is indeed the president of this country.

Country F consists of $n$ cities. These $n$ cities are connected by $n-1$ bidirectional roads. It is guaranteed that starting from any city, you can reach any other city through these $n-1$ bidirectional roads.

Of course, using these bidirectional roads costs money. Passing through the $i$-th bidirectional road costs $c_i$ yuan. We call $c_i$ the cost of the $i$-th bidirectional road.

We define $cost(x,y)$ as the sum of the costs of all bidirectional roads on the simple path from city $x$ to city $y$. In particular, when $x=y$, $cost(x,y)=0$.

To promote the development of Country F, Little C built a new city $n+1$. Now he needs to build one more bidirectional road so that city $n+1$ can also reach any city through these $n$ bidirectional roads.

He has a total of $q$ road-building plans. Each plan provides two parameters $k_i,w_i$. For each plan, you need to compute, after building a bidirectional road connecting city $k_i$ and city $n+1$ with cost $w_i$, the sum of all $cost(i,j)$, i.e. $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$.

Since the answer may be very large, you only need to output the result modulo $998244353$.

The plans are independent of each other, meaning none of the plans will affect the existing roads, and these plans will not actually be carried out.

Input Format

The first line contains two integers $n,q$.

The next $n-1$ lines: the $i$-th line contains three integers $u_i,v_i,c_i$, indicating that there is a bidirectional road connecting city $u_i$ and city $v_i$ with cost $c_i$.

The next $q$ lines: the $i$-th line contains two integers $k_i,w_i$, indicating a plan for building a new road.

Output Format

Output $q$ lines, each containing one integer. The integer on the $i$-th line denotes, after building a bidirectional road connecting city $k_i$ and city $n+1$ with cost $w_i$, the sum of all $cost(i,j)$ modulo $998244353$, i.e. $\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

Hint

Sample Explanation #1

After building a bidirectional road connecting city $1$ and city $5$ with cost $2$, the roads of Country F are as shown in the figure below:

For example, in this case, $cost(4,5)=9$ and $cost(1,3)=5$.

It is easy to obtain that $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$.

Sample #3

See city/city3.in and city/city3.ans in the additional files.

This sample satisfies the constraints of test point $4$.

Sample #4

See city/city4.in and city/city4.ans in the additional files.

This sample satisfies the constraints of test point $11$.

Sample #5

See city/city5.in and city/city5.ans in the additional files.

This sample satisfies the constraints of test point $14$.

Sample #6

See city/city6.in and city/city6.ans in the additional files.

This sample satisfies the constraints of test point $20$.

Constraints

For $100\%$ of the data, $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$. It is guaranteed that starting from any city, you can reach any other city through the original $n-1$ bidirectional roads.

Special Property A: It is guaranteed that for all $1 \le i \lt n$, $u_i=i,v_i=i+1$.

Special Property B: It is guaranteed that for all $1 \le i \le q$, $k_i=1$.

Translated by ChatGPT 5