说明

小 Z 最近沉迷于一款游戏：《浴火银河：联盟》。在这个游戏中，你可以拥有很多星球。每个星球上都可以开采资源，而运输资源则需要通过母舰在星球间飞行来实现。经过探索，小 Z 发现以当前自己所拥有的 $n$ 个星球（编号 $1\sim n$）而言，走其中 $m$ 条路线是最合适的。在宇宙中航行没有方向的限制，所以这 $m$ 条路线都是双向的。由于小 Z 的运营不太好，所以这些最合适的路线不保证能连接所有 $n$ 个星球，但聪明的小 Z 绝不会让某两个星球间有多于一条路线连接，也不会让一条路线的两端是同一个星球。

由于各个星球开采资源的能力不同，这些路线都有各自的重要程度 $W$，代表了这条路线的价值。同时，有丰富的游戏经验的小 Z 发现，在游戏中，为了使自己的资源运输达到最优的状态，需要在这 $m$ 条较好的路线选择恰好 $n-1$ 条，使得自己所拥有的 $n$ 个星球联通。当然，有很多种方法来选择这 $n-1$ 条路线，每种选择方法 $P$ 为这 $m$ 条边的一个大小为 $n-1$ 子集。根据经验，小 Z 定义每种选择方法的优秀程度为 $V_P = \prod W_p (p \in P)$。聪明的小 Z 很快就找到了优秀程度最大的选择方法，但另一个问题却困扰了他：如何求出这些选择方法的优秀程度的平均值？

由于小 Z 很讨厌小数，所以他只想知道这个平均值 $Ans$ 在模 $998244353$ 意义下的值。

（提示：可以证明 $Ans = p/q (p, q \in \mathbb{N})$，那么你输出的是一个整数 $s$，满足 $0 \le s < 998244353$ 并且 $s \cdot q \equiv p \pmod{998244353}$）

输入格式

第一行两个整数 $n, m$，表示星球数量和最合适的路线条数。

接下来 $m$ 行，每行三个数 $a, b, c$，表示每条双向路线连接的两个星球编号。

输出格式

一行一个整数 $s$，表示问题描述中的输出。

3 2
1 3 5
2 1 6

30

7 7
7 6 126
3 7 826
1 2 909
5 6 665
2 3 768
1 4 301
1 3 365

63511277

提示

【样例 1 说明】

显然 $m = n-1$ 时，只有一种选择方法，优秀程度为 $5 \times 6 = 30$，所以输出为 $30$。

【数据规模和约定】

对于前 $15\%$ 的数据：满足 $n, m \le 15$；

对于前 $40\%$ 的数据：满足 $n, m \le 50$；

另有 $10\%$ 的数据：满足 $m \le n$；

对于所有数据：满足 $n \le 300$ 并且 $n-1 \le m \le 1000, n \ge 2$，每条路线的重要程度 $0 \le c < 998244353$。