Problem Description

Xiao Z has recently become addicted to a game: Galaxy on Fire: Alliances. In this game, you can own many planets. Resources can be mined on each planet, and transporting resources is done by flying a mothership between planets. After exploring, Xiao Z found that, for the $n$ planets he currently owns (numbered $1 \sim n$), it is best to use exactly $m$ routes. Traveling in space has no direction restrictions, so these $m$ routes are all bidirectional. Because Xiao Z is not very good at managing things, these optimal routes are not guaranteed to connect all $n$ planets. However, smart Xiao Z will never allow more than one route between any two planets, and will never allow a route whose two ends are the same planet.

Since different planets have different mining abilities, each route has its own importance value $W_i$, representing the value of this route. At the same time, with his rich gaming experience, Xiao Z found that, in order to make his resource transportation optimal, he needs to choose exactly $n - 1$ routes from these $m$ good routes so that his $n$ planets become connected. Of course, there are many ways to choose these $n - 1$ routes. Each choice method $P$ is a subset of the $m$ edges with size $n - 1$. Based on experience, Xiao Z defines the excellence of each choice method as $V_P = \prod W_p (p \in P)$. Smart Xiao Z quickly found the choice method with the maximum excellence, but another problem troubles him: how to compute the average value of the excellence over all these choice methods?

Since Xiao Z really dislikes decimals, he only wants to know this average value $Ans$ modulo $998244353$.

(Hint: It can be proved that $Ans = p/q (p, q \in \mathbb{N})$, then you should output an integer $s$ such that $0 \le s < 998244353$ and $s \cdot q \equiv p \pmod{998244353}$.)

Input Format

The first line contains two integers $n, m$, representing the number of planets and the number of optimal routes.

The next $m$ lines each contain three numbers $U_i, V_i, W_i$, representing the two planet indices connected by the $i$-th bidirectional route and the importance value of this route.

Output Format

Output one integer $s$, which is the output described in the statement.

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

Hint

Sample 1 Explanation

Obviously, when $m = n - 1$, there is only one choice method, and the excellence is $5 \times 6 = 30$, so the output is $30$.

Constraints

For the first $15\%$ of the testdata: $n, m \le 15$.

For the first $40\%$ of the testdata: $n, m \le 50$.

There is another $10\%$ of the testdata: $m \le n$.

For all testdata: $n \le 300$ and $n - 1 \le m \le 1000$, $n \ge 2$. The importance value of each route satisfies $0 \le c < 998244353$.

Translated by ChatGPT 5