分数: 600 点
问题陈述
给定一个无向图 N 顶点和 M 边缘。的 i第一条边连接顶点 A_i 和 B_i 的重量为 C_i.
最初,所有顶点都涂成黑色。您最多可以进行以下操作 K 次。
- 操作:选择任意顶点 v 和任何整数 x。将从顶点可到达的所有顶点涂成红色 v 通过遍历权重最多为 x,包括 v 本身。
运算后涂成红色的顶点集可以有多少组?
求计数模数 998244353.
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K A_1 B_1 C_1 \vdots A_M B_M C_M
输出
打印答案。
示例输入 1
3 2 1 1 2 1 2 3 2
示例输出 1
6
例如,操作 (v,x)=(2,1) 绘制顶点 1,2 红色,并进行操作 (v,x)=(1,0) 绘制顶点 1.
最多一次操作后,涂成红色的顶点集可以是以下六种之一: \{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}.
示例输入 2
5 0 2
示例输出 2
16
给定的图形可能未连接。
示例输入 3
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
示例输出 3
40
给定的图可能具有多边和自环。