Description

You are given a graph with $n$ vertices and $m$ edges, guaranteed to have no multiple edges and no self-loops. The $i$-th edge has weight $w_i$.

Define an edge set as good if and only if the graph formed by taking these edges and the vertices incident to them does not contain two or more different cycles within the same connected component (two cycles are considered different if their edge sets are not completely identical). Also define the weight of an edge set as the sum of the weights of all edges in the set.

Now, each edge disappears with probability $50\%$. After the disappearance process ends, find the expected value of the weight of the maximum-weight good edge set in the remaining graph.

Output this expected value modulo the large prime $998244353$.

It can be shown that this expected value is a rational number. Its value modulo $998244353$ is obtained by writing it in lowest terms $\frac{x}{y}$ (where $x$ and $y$ are coprime), and then computing $x \times y^{998244351} \bmod 998244353$.

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and edges of the graph.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, describing the two endpoints of the $i$-th edge and its weight.

Output Format

Output one positive integer on one line, representing the answer.

4 6
2 3 294405877
3 4 340909188
1 2 7718822
2 4 340754548
1 4 209906514
1 3 810986947

121593921

Hint

Constraints

• For the first $20\%$ of the testdata, $n \le 10$, $m \le 20$;
• For the first $40\%$ of the testdata, $n \le 10$, $m \le 30$;
• For another $30\%$ of the testdata, all edge weights are equal;
• For all testdata, $1 \le n \le 15$, $1 \le m \le 60$, $1 \le u_i, v_i \le n$, $0 \le w_i < 998244353$.

Translated by ChatGPT 5