#P7605. [2018年杭电多校]Variance-MST

    ID: 7618 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800最小生成树LCT数学排序构造图论

[2018年杭电多校]Variance-MST

Variance-MST

Problem Description

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

Input

The first line contain a integer TT (no morn than 10), the following is TT test case, for each test case : First line contains two positive integer nn and mm denoting the number of vertices and edges of the graph. Each of the following mm lines contains three positive integers uiu_{i} , viv_{i} , wiw_{i},denoting the ithi_{th} edge connects the vertices uiu_{i} and viv_{i} with the weight wiw_{i}. It is guaranteed the graph is connected. 2≤n≤1000002 \leq n \leq 100000 1≤m≤2000001 \leq m \leq 200000 1≤ui,vi≤n1 \leq u_{i}, v_{i} \leq n ui≠viu_{i} \ne v_{i} 0≤wi≤1000000 \leq w_{i} \leq 100000 It is guaranteed that sum of n less than 400000, m less than 600000.

Output

Let P/QP / Q be the number of correct answers, represented as an irreducible fraction. Print PQ−1PQ^{-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