背景

JP和JPY被传送到了一棵树上
JPY获得了这棵树的地图
但他不知道自己在哪
JPY想知道他和JP的期望距离
(单位：nm)

描述

给出一棵N个点的树，边有边权
求树上随机二点的期望距离
当然对于JPY来说他只想知道
这个期望模998244353的值

输入

第一行两个正整数N, M
接下来N-1行每行三个正整数a, b, c
表示a与b之间有一条长度为c的边相连
接下来M行每行三个正整数a, b, c
表示a到b的路径上所有边长度+c

输出

输出M+1行
第一行一个正整数为原树上随机路径长度期望
接下来M行每行一个正整数为修改后的期望
对998244353取模

样例

输入

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

输出

221832082
443664164
221832086

解释

对于原图
(1, 1)=0; (1, 2)=3; (1, 3)=5;
(2, 1)=3; (2, 2)=0; (2, 3)=8;
(3, 1)=5; (3, 2)=8; (3, 3)=0;
Ans=(0+3+5+3+0+8+5+8+0)/(3*3)=32/9
而221832082*9=998244353*2+32
后两行分别为64/9和68/9，分析方法类似

范围

30% N<=300 M<=300
60% N<=3000 M<=5000
80% N<=10000 M<=10000
100% N<=\(10^6\) M<=\(5\ast 10^5\) 1<=a,b<=N 0<=c<=1000

限制

2000ms
128M