配点 : $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$

出力

答えを出力せよ。

3 2 1
1 2 1
2 3 2

6

例えば $(v,x)=(2,1)$ と選んで操作を行うと、頂点 $1,2$ を赤く塗ることができ、$(v,x)=(1,0)$ と選んで操作を行うと、頂点 $1$ を赤く塗ることができます。

高々 $1$ 回の操作の後で赤く塗られている頂点の集合としてあり得るものは $\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$ の $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

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