题目描述

A 国由 $n$ 座城市与 $n-1$ 条双向道路组成，每条道路连接两个不同的城市。保证任意两座城市都可以通过若干条道路相互到达。

和平外表下，政治的暗流正在涌动。A 国的反动分子日益猖獗，为了减小将来的损失，A 国政府决定在一些城市驻军以应对可能的动乱。具体来说，A 国政府将选择一条包含恰好 $k$ 座城市的路径，并在路径上的每座城市驻军。

动乱会发生在 $n$ 座城市中的一座。发生后，政府将从距离动乱城市最近的驻军城市出兵，到达动乱城市所需的时间为出兵城市到动乱城市路径上道路长度之和。

政府不知道动乱会发生在哪座城市，所以假设所有城市发生动乱的概率相等。对于一种驻军方案，其损失值为发生动乱后到达动乱城市所需时间的期望。

求最小的损失值对 $998244353$ 取模的结果。如果不存在一种驻军方案，输出 $-1$。

输入格式

第一行两个整数 $n,k$。

接下来 $n-1$ 行，每行三个整数 $x_i,y_i,z_i$，表示第 $i$ 条道路连接 $x_i,y_i$，长度为 $z_i$。

输出格式

一个整数，表示答案。

样例一

input

3 2
1 2 1
1 3 2

output

332748118

explanation

在城市 $1,3$ 驻军，若动乱发生在城市 $1$ 或 $3$，所需时间为 $0$；若动乱发生在城市 $2$，所需时间为 $1$。损失值为 $\frac{1}{3}$。

样例二

input

5 2
5 2 5
3 5 10
4 2 3
1 5 7

output

4

限制与约定

对于所有数据，满足 $1\le k\le n\le 2\times 10^6$，$1\le x_i,y_i\le n$，$1\le z_i\le 10^6$。

由于读入量较大，下发文件中包含了快速的读入方式，选手可以选择使用。