加权图涂色

题目描述

给定一个无向图，它有 $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$

输出格式

输出答案。

样例

3 2 1
1 2 1
2 3 2

6

例如，执行 $(v,x)=(2,1)$ 的操作会把顶点 $1,2$ 涂成红色，执行 $(v,x)=(1,0)$ 的操作会把顶点 $1$ 涂成红色。

最多执行一次操作后，被涂成红色的顶点集合可能是以下 6 种之一：$\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$。

5 0 2

16

给定的图可能不是连通的。

6 8 2
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 1 3
1 2 10
1 1 100

40

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

数据范围

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