题目描述

$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$

输出格式

答えを出力せよ。

题目大意

给定一个 $n$ 个点 $m$ 条边的无向带权图，初始时点全为黑色。

你可以在这张图上进行不超过 $k$ 次操作，每次操作可被描述为如下形式：

1. 选择一个点 $u$ 和一个整数 $x$。
2. 将所有从点 $u$ 出发，只经过边权不大于 $x$ 的边 能到达的所有点 $v$ 染红。

设所有被染红的点构成的点集为 $S$，求不超过 $k$ 次操作后能构成多少个不同的 $S$。答案对 $998244353$ 取模。

两个集合 $S_1,S_2$ 被视为不同当且仅当存在一个元素 $e$，其只属于 $S_1,S_2$ 中的一个。

3 2 1
1 2 1
2 3 2

6

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\ \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$
• 入力に含まれる値は全て整数である

Sample Explanation 1

例えば $(v,x)=(2,1)$ と選んで操作を行うと、頂点 $1,2$ を赤く塗ることができ、$(v,x)=(1,0)$ と選んで操作を行うと、頂点 $1$ を赤く塗ることができます。 高々 $1$ 回の操作の後で赤く塗られている頂点の集合としてあり得るものは $\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$ の $6$ つです。

Sample Explanation 2

与えられるグラフは連結とは限りません。

Sample Explanation 3

与えられるグラフは多重辺や自己ループを持つかもしれません。