Expected Maximum Weight Pseudoforest

Given an undirected graph with (n) vertices and (m) edges, where each edge (i) has a weight (w_i) (there are no self-loops or multiple edges), we define an edge set to be good if and only if the graph induced by these edges (and their incident vertices) does not contain two or more different cycles in any single connected component. In other words, every connected component can have at most one cycle. The weight of an edge set is the sum of the weights of its edges.

Now, each edge independently disappears with a probability of 50%. Let (F) be the maximum total weight of any good edge set in the graph obtained after the random removal process. It can be shown that (F) is a rational number. Write (F) in simplest form as (\frac{x}{y}) (with (x) and (y) coprime), and output (x \times y^{998244351}) modulo (998244353).

A useful observation is that a good edge set is essentially a maximum spanning pseudoforest: it is optimal to take the maximum spanning forest of the remaining graph (which contributes the sum of the weights of the chosen tree edges) and, in each connected component, add at most one extra edge (if any) to form a cycle (but not more than one per component).

inputFormat

The first line contains two integers (n) and (m). Each of the next (m) lines contains three integers (u), (v) and (w), representing an edge connecting vertices (u) and (v) with weight (w). The vertices are numbered from 1 to (n).

outputFormat

Output a single integer which is the expected maximum weight of a good edge set in the graph after the disappearance process, modulo (998244353).

sample

3 3
1 2 3
2 3 2
3 1 1

3