← 返回题目列表

AtCoder · abc235_h

Ex. 绘制加权图

中文机器翻译题面 查看原题

分数: 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

给定的图可能具有多边和自环。