Time Limit : sec, Memory Limit : KB
Japanese

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 のスコアを得られる.

Note

Commentary