You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

寒冷的保加利亚小屋里，你发现了寒妖王给你提出的一个问题。

题目描述

给定一张 $n$ 个点 $m$ 条边的图，保证无重边与自环。第 $i$ 条边有权值 $w _i$。

定义一个边集是好的，当且仅当将这些边和与这些边相连的点取出来形成的图没有两个或以上处在同一个连通块的不同的环（两个环不同指的是构成环的边集不能完全相同）。同时定义一个边集的权值为边集中所有边的边权之和。

现在，每条边均有 $50\%$ 的概率消失。求在消失过程完成后，图中权值最大的好边集的权值的期望。

输出该期望值对一个大质数 $998244353$ 取模的结果。

可以知道这里的期望值是一个有理数。其对 $998244353$ 取模的结果相当于是将其写为最简分数形式 $\frac x y$（其中 $x$ 与 $y$ 互质）后 $x \times y ^{998244351}$ 对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n, m$，表示该图的点数和边数。

接下来 $m$ 行，每行三个整数 $u _i, v _i, w_i$，分别描述了图中第 $i$ 条边的两个端点与这条边的权值。

输出格式

一行一个正整数表示答案。

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

121593921

提示

「数据范围与约定」

• 对于前 $20\%$ 的数据，保证 $n \le 10$，$m \le 20$；
• 对于前 $40\%$ 的数据，保证 $n \le 10$，$m \le 30$；
• 对于另外 $30\%$ 的数据，保证所有边的权值均相等；
• 对于所有数据，保证 $1 \le n \le 15$，$1 \le m \le 60$，$1 \le u _i, v _i \le n$，$0 \le w _i < 998244353$。