Variance-MST

Problem Description

Given a edge-weighted graph, your task is to compute the spanning tree with the smallest variance. Formally, if $w_{e}$ denotes the weight of edge $e$ then the variance of the tree with $n$ vertices is $\frac{\sum\limits_{e}(w_e - A)^{2}}{n - 1}$, where $A = \sum\limits_{e}\frac{w_e}{n - 1}$

Input

The first line contain a integer $T$ (no morn than 10), the following is $T$ test case, for each test case : First line contains two positive integer $n$ and $m$ denoting the number of vertices and edges of the graph. Each of the following $m$ lines contains three positive integers $u_{i}$ , $v_{i}$ , $w_{i}$,denoting the $i_{th}$ edge connects the vertices $u_{i}$ and $v_{i}$ with the weight $w_{i}$. It is guaranteed the graph is connected. $2 \leq n \leq 100000$ $1 \leq m \leq 200000$ $1 \leq u_{i}, v_{i} \leq n$ $u_{i} \ne v_{i}$ $0 \leq w_{i} \leq 100000$ It is guaranteed that sum of n less than 400000, m less than 600000.

Output

Let $P / Q$ be the number of correct answers, represented as an irreducible fraction. Print $PQ^{-1}$ modulo 998244353. each test case one line.

Sample Input

1

4 6

1 2 2

1 3 4

2 3 6

4 1 7

4 2 5

4 3 3

Sample Output

665496236

Source

2018 Multi-University Training Contest 6