太难不研究

题目背景

Y同学正在研究一张极为复杂的网络图。在这张图中，信号以一种奇特的方式传播。一次信号的激发会点亮网络中的一个区域。经过多次激发后，整个网络会呈现出不同的点亮模式。Y同学对这些模式产生了浓厚的兴趣，他想知道，通过有限次数的激发，总共能产生多少种不同的最终点亮模式。

题目描述

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

初始时，所有节点都处于“未激活”状态。Y同学可以执行一种“激活操作”，总共可以执行至多 $K$ 次。

一次激活操作定义如下：

• 选择一个节点 $v$（$1 \le v \le N$）和一个非负整数阈值 $x$。
• 所有从节点 $v$ 出发，仅通过权值不超过 $x$ 的边所能到达的全部节点（包括 $v$ 自身），都将被“激活”。

一个节点一旦被激活，在后续操作中将一直保持激活状态。换言之，最终被激活的节点集合是所有单次操作所激活的节点集合的并集。

Y同学想知道，在执行了至多 $K$ 次操作后，可能得到的不同最终激活节点集合一共有多少种？请输出方案数对 $998244353$ 取模后的结果。

输入格式

输入的第一行包含三个整数 $N, M, K$，分别表示节点数量、边的数量和操作次数的上限。

接下来 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，描述一条连接节点 $A_i$ 和 $B_i$ 且权值为 $C_i$ 的无向边。

输出格式

输出一个整数，表示不同激活节点集合的方案数，对 $998244353$ 取模。

样例

样例输入 1

3 2 1
1 2 1
2 3 1

样例输出 1

5

样例输入 2

5 3 2
1 2 10
2 3 20
4 5 15

样例输出 2

26

样例输入 3

4 3 2
1 2 10
2 3 10
3 4 20

样例输出 3

13

提示

样例 1 解释

图中有两个权值为 $1$ 的边 (1,2) 和 (2,3)。最多可以操作 $1$ 次。 可能得到的不同激活节点集合如下：

1. 执行 $0$ 次操作：激活集合为 $\emptyset$。
2. 执行 $1$ 次操作：
   • 选择 $v=1, x=0$：激活集合为 $\{1\}$。
   • 选择 $v=2, x=0$：激活集合为 $\{2\}$。
   • 选择 $v=3, x=0$：激活集合为 $\{3\}$。
   • 选择任意节点 $v \in \{1,2,3\}$ 和 $x \ge 1$：由于所有边权均为 $1$，所有节点都会被激活，激活集合为 $\{1,2,3\}$。

综上，不同的激活节点集合有 $\emptyset, \{1\}, \{2\}, \{3\}, \{1,2,3\}$，共 $5$ 种。

数据范围与约定

对于所有测试数据，保证：

• $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$
• 输入的所有数值均为整数。

说明

• 给定的图可能不连通，也可能包含重边或自环。
• 请注意，最终的激活节点集合是所有单次操作产生的激活节点集合的并集。
• “至多 $K$ 次操作”也包括执行 $0$ 次操作的情况（此时没有节点被激活，激活节点集合为空集）。