Variance-MST

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}$

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.

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

each test case one line.

1
4 6
1 2 2
1 3 4
2 3 6
4 1 7
4 2 5
4 3 3

665496236

2018 Multi-University Training Contest 6