Sum of Powered Spanning Tree Weights

Little S has just learned about spanning trees and came up with the following problem:

Given a weighted undirected complete graph with n vertices and a positive integer k, a spanning tree’s weight is defined as the sum of the weights of its edges. Compute the sum of the k-th power of the weight for every spanning tree. Since the answer can be very large, output it modulo \(998244353\).

The input guarantees that the graph is complete; hence, there will be exactly \(\frac{n(n-1)}{2}\) edges provided.

inputFormat

The first line contains two integers n and k (number of vertices and the exponent).

Then \(\frac{n(n-1)}{2}\) lines follow, each containing three integers u, v and w, which represent an undirected edge connecting vertex u and vertex v with weight w. It is guaranteed that \(1 \le u, v \le n\) and every pair \(u < v\) appears exactly once.

outputFormat

Output a single integer, the sum of the k-th powers of the weights of all spanning trees of the given graph, taken modulo \(998244353\).

sample

3 2
1 2 1
1 3 2
2 3 3

50