AT_abc235_h.[ABC235Ex] Painting Weighted Graph

给定一个包含 $N$ 个顶点和 $M$ 条边的无向图。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，权值为 $C_i$。

最初，所有顶点都被涂成黑色。你最多可以进行 $K$ 次如下操作：

• 操作：任选一个顶点 $v$ 和一个整数 $x$。将从顶点 $v$ 出发，只经过权值不超过 $x$ 的边能够到达的所有顶点（包括 $v$ 本身）涂成红色。

问经过操作后，可能作为红色顶点集合的不同方案有多少种？请输出方案数对 $998244353$ 取模的结果。

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

请输出答案。

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq K \leq 500$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 输入中的所有数均为整数

样例解释 1

例如，选择 $(v, x) = (2, 1)$ 进行操作时，可以将顶点 $1, 2$ 涂成红色；选择 $(v, x) = (1, 0)$ 进行操作时，可以将顶点 $1$ 涂成红色。最多进行 $1$ 次操作后，可能的红色顶点集合有 $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,2,3\}$ 共 $6$ 种。

样例解释 2

给定的图不一定是连通的。

样例解释 3

给定的图可能包含重边或自环。

由 ChatGPT 4.1 翻译