I: Islands Survival

問題

$N$ 頂点 $M$ 辺の単純連結無向グラフがある． 頂点には $1, 2, \dots, N$ と番号がつけられている． 辺には $1, 2, \dots, M$ と番号がつけられており，辺 $i$ は頂点 $a_i$ と $b_i$ をつないでいる． また，辺 $i$ は時刻 $t_i$ に消える．どの辺も通過するために単位時間がかかる． あなたは最初，時刻 0 において頂点 1 にいる． あなたは最適に行動することで，時刻 $T$ までに得られるスコアを最大化したい． スコアは最初 0 であり，イベントは以下に従って起きる．

1. 今の時刻 $t'$ が $t' \geq T$ を満たすならば終了する．そうでなければ 2. へ．
2. $t_i = t'$ なるすべての辺 $i$ が消える．
3. あなたがいる頂点を $v$ とするとき，頂点 $v$ を含む連結成分に含まれる頂点数を $x$ とすると，スコアに $x$ が加算される．
4. あなたは頂点 $v$ と隣接している頂点のいずれかに移動するか，頂点 $v$ に留まる．ただし前者の場合，既に消えた辺を使うことはできない．
5. $t' \gets t' + 1$ として 1. へ．

得られるスコアの最大値を求めよ．

制約

• $2 \le N \le 10^5$
• $N - 1 \le M \le \min(2 \times 10^5, N(N - 1) / 2)$
• $1 \le T \le 10^5$
• $1 \le a_i , b_i \le N$
• $1 \le t_i \le T$
• 与えられるグラフは単純かつ連結．

入力形式

入力は以下の形式で与えられる．

$N \ M \ T$
$a_1 \ b_1 \ t_1$
$\vdots$
$a_M \ b_M \ t_M$

出力

スコアの最大値を出力せよ．また，末尾に改行も出力せよ．

サンプル

サンプル入力1

5 4 2
1 2 2
2 3 1
1 4 2
4 5 1

サンプル出力1

8

時刻 0 に 5，時刻 1 に 3 のスコアを得られる．

サンプル入力2

4 4 3
1 2 2
2 3 1
3 4 3
4 1 1

サンプル出力2

8

時刻 0 に 4，時刻 1 に 2，時刻 2 に 2 のスコアを得られる．