在你的帮助下，跳蚤国王发现把小队排列成理想情况是不可能的，于是他放弃了让小队重新排列的计划，直接下令强攻实验室。

在经过一番血战之后，跳蚤军队成功攻克了实验室中的大部分区域并把 picks 博士与他的猴子们逼入了最后一间房间中——同时也是存储了绝大部分资料和研究成果的最重要的房间。

这间房间的建造利用了跳蚤夸克神奇的力量，因此跳蚤国王发现强行闯入房间是不可能的，而唯一的入口——房间正门却被一个密码锁锁住了。

在这个密码锁上画了一张 $n$ 个点的完全图，其中每一条边旁边都写了一个数字。跳蚤国王发现只有 $m$ 条边对应的数字不是 $5000$（其他数字都是 $5000$）。

经过一番探索，跳蚤国王发现这个密码锁的密码等于这样一个问题的答案：

密码锁上给出了一张 $n$ 个点的完全图，现在要给这个完全图的每一条边随机定向成一个有向图。对于一条边 $(i,j)(i < j)$，这条边的方向是 $i$ 到 $j$ 的概率是 $\frac{\mathrm{num}_{i,j}}{10000}$，$\mathrm{num}_{i,j}$ 指这条边旁边的数字，否则就是 $j$ 到 $i$。在随机定向后，设这张有向图的强连通分量数目为 $x$，求 $x \times 10000^{n(n-1)}$ 的期望，可以证明该期望值一定是一个整数。因为答案可能很大，所以只需要求出这个答案对 $998244353（7\times 17 \times 2^{23}+1$，一个质数$）$ 取模后的结果。

跳蚤国王发现这个问题并不是非常简单，于是他让你——这附近最著名的民间科学家来帮他计算这个问题的答案。

输入格式

第一行两个正整数 $n, m$，含义如题意所述。

接下来的$m$行中，第$i$行有三个整数$u_i, v_i, w_i$，表示边$(u_i, v_i)$上的数字是$w_i$。保证 $u_i < v_i$ 。

输出格式

输出期望值对 $998244353$ 取模后的值。

样例一

input

2 1
1 2 4096

output

200000000

explanation

图中只有一条边，有$ \frac{4096}{10000} $的概率是从 $1$ 到 $2$，有$ 1 - \frac{4096}{10000} $的概率是从 $2$ 到 $1$。但是无论怎么定向该有向图连通分量数目都是 $2$，所以答案为$ 2 \times 10000 ^ {2 \times 1} = 200000000 $。

样例二

input

3 3
1 2 4000
2 3 6000
1 3 3000

output

296883784

explanation

图中有三条边，定向概率均已给出，容易发现有$ \frac{4000}{10000} \times \frac{6000}{10000} \times (1 - \frac{3000}{10000}) + (1 - \frac{4000}{10000}) \times (1 - \frac{6000}{10000}) \times \frac{3000}{10000} = 0.24$的概率图中只有一个强连通分量，$1 - 0.24 = 0.76$的概率图中有三个强连通分量，而$ 10000 ^ {3 \times 2} = 10 ^ {24} $，所以答案为$ 0.24 \times 1 \times 10 ^ {24} + 0.76 \times 3 \times 10 ^ {24} = 2,520,000,000,000,000,000,000,000 $，注意答案要模 $998244353$ 后输出，因此答案为 $296883784$。

样例三

input

6 15
1 2 10000
1 3 0
1 4 10000
1 5 10000
1 6 10000
2 3 10000
2 4 10000
2 5 10000
2 6 10000
3 4 10000
3 5 10000
3 6 10000
4 5 10000
4 6 0
5 6 10000

output

500494593

explanation

可以发现定向的图是固定的，只有$ \{1, 2, 3\} $和 $ \{4, 5, 6\} $两个强连通分量，因此答案为$2 \times 10000 ^ {6 \times 5}$，注意对$ 998244353 $取模。

样例四

input

4 0

output

99696143

explanation

注意没有输入的边的两个方向的定向概率均为$ 0.5 $。

样例五

input

5 4
1 5 10000
1 4 10000
1 3 10000
1 2 10000

output

985337417

explanation

容易看出期望强连通分量数是前一个图的期望强连通分量数加1，但是题目求的是强连通分量数乘以$10000 ^ { n(n - 1) }$的期望，因此答案相差甚远。

样例六

input

4 4
1 2 4194
1 3 9971
2 4 7191
1 4 1102

output

433654756

样例七

input

13 7
1 2 3
4 5 6
7 8 9
10 11 12
1 13 15
3 4 18
5 6 21

output

940436965

限制与约定

对于所有数据， $1 \le n \le 38$, $0 \le m \le 19$, $0 \le w_i \le 10000$。

对每一个$i$, 均有$u_i < v_i$。

对于$i \neq j$，保证$u_i \neq u_j$或$v_i \neq v_j$，即没有重边，这意味着$m \le \frac{n(n - 1)}{2}$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载