图上的数

Problem Description

给出一个 $n$ 个点 $m$ 条边的有向无环图（不保证将有向边视为无向边之后联通）。第 $i$ 条边有一个权重 $p_i = P_i / 10000$（其中 $P_i$ 是区间 $[0, 10000]$ 内的非负整数）。 初始时，你有一个空的二进制数字（长度 $\mathrm{len} = 0$），每当经过第 $i$ 条边时：

• 你有 $p_i$ 的概率获得 $1$，有 $1 - p_i$ 的概率获得 $0$。
• 获得的数字将会被均匀随机地插入到 $\mathrm{len} + 1$ 个空隙位置的其中一个上，然后令 $\mathrm{len} \gets \mathrm{len} + 1$。 你可以任取一个起点和一个终点，自己确定一条从起点到终点的路径。求经过这条路径后，收获数字的最大期望（答案对 $998244353$ 取模）。 需要注意的是，你需要预先选择路径后再行动，而不能在行动时决策下一步的行动。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 550)$，表示数据组数。对于每组测试数据： 第一行两个正整数 $n, m(1 \leq n \leq 10^5, 1 \leq m \leq 4 \times 10^5)$，分别表示有向无环图的点数和边数。 接下来 $m$ 行，每行三个整数 $x_i, y_i, P_i(1 \leq x, y \leq n, 0 \leq P_i \leq 10000)$，表示有一条从 $x$ 到 $y$ 权重为 $p_i = P_i / 10000$ 的有向边，不保证没有重边。 保证所有测试数据中 $n$ 之和不超过 $3.1 \times 10^5$，$m$ 之和不超过 $9 \times 10^5$。

Output

对于每组测试数据：输出一行一个整数，表示最大期望对 $998244353$ 取模后的值。

Sample Input

2
3 3
1 3 4
1 2 1
2 3 2
3 3
1 3 6
1 2 1
2 3 2

Sample Output

92187866
788413390

Hint

样例 $1$ 路径选择：$1 \to 2 \to 3$。 样例 $2$ 路径选择：$1 \to 3$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）