Product of MST Weights

You are given an undirected graph with n nodes and m edges. Each edge has an associated positive weight. Your task is to compute the product of the weights of the edges in the graph's minimum spanning tree (MST). Note that the product should be computed modulo \(998244353\).

If the graph contains no edges (i.e. \(m = 0\)), then output 1. It is guaranteed that \(1 \leq n \leq 1000\) and \(0 \leq m \leq 10000\). Each edge is given as a triple \((u, v, w)\) where \(1 \leq u, v \leq n\) and \(1 \leq w \leq 1000\).

Recall that a minimum spanning tree (MST) of a connected graph is a subset of the edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. In this problem, instead of the sum, you are required to output the product of the weights of the chosen edges modulo \(998244353\).

inputFormat

The input is given via standard input with the following format:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm

Where the first line contains two integers \(n\) and \(m\), and each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) indicating an edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer: the product of the weights of all the edges in the MST, computed modulo \(998244353\). If there are no edges (\(m = 0\)), output 1.

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

6