AT_abc235_h [ABC235Ex] Painting Weighted Graph

[problemUrl]: https://atcoder.jp/contests/abc235/tasks/abc235_h $ 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 $

答えを出力せよ。

### 制約 - $ 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 与えられるグラフは多重辺や自己ループを持つかもしれません。