D - Poor Sense of Direction

問題

Loop 王国は $N$ 個の街と $M$ 本の道路からなり、街には $1$ から $N$ までの番号が付いています。
$i$ 番目 $(1 \leq i \leq M)$ の道路は街 $u_i$ と街 $v_i$ を双方向に結んでおり、通るのに $t_i$ 分かかります。

Alice さんは街 $N$ に辿り着くまで、街から出ている全ての道路から一様ランダムに $1$ 本選び、その道路を通って別の街に移動する行動を繰り返します。
Alice さんは、道を通っているときに立ち止まったり引き返したりすることはなく、道路を選ぶときにかかる時間は無視できます。
そして、街 $N$ に辿り着いた後はずっと街 $N$ に滞在します。

Alice さんは現在街 $1$ にいます。 $T$ 分以内に街 $N$ に辿り着く確率を $\mathrm{mod} \ 998244353$ で求めてください。

確率 $\mathrm{mod} \ 998244353$ とは

この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $\frac{y}{x}​$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。

このとき $xz \equiv y \ (\mathrm{mod} \ 998244353)$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を答えてください。

制約

• $2 \leq N \leq 1000$
• $1 \leq M \leq 1000$
• $1 \leq T \leq 2000$
• $1 \leq u_i < v_i \leq N$
• $i \ne j \Longrightarrow (u_i, v_i) \ne (u_j, v_j)$
• $1 \leq t_i \leq T$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル 1

3 3 3
1 2 2
1 3 1
2 3 1

249561089

例えば、 Alice さんは以下の行動で街 $3$ に $3$ 分以内で辿り着きます。

1. 街 $1$ から道路 $1$ を通って、街 $2$ に $2$ 分かけて行く。
2. 街 $2$ から道路 $2$ を通って、街 $3$ に $1$ 分かけて行く。

Aliceさんは $\frac{3}{4}$ の確率で時間内に街 $3$ に辿り着くことができます。よって、 $4 \times 249561089 \equiv 3 \ (\mathrm{mod} \ 998244353)$ を満たすため、答えとして $249561089$ を出力します。

サンプル 2

2 1 1000
1 2 1

1

絶対に時間内に辿り着けます。

サンプル 3

6 10 100
1 3 12
1 4 3
2 3 4
2 4 32
2 5 16
2 6 100
3 4 10
3 5 100
4 6 64
5 6 20

218482382