problem

There is a simple concatenated undirected graph with $ N $ vertices and $ M $ edges. The vertices are numbered $ 1, 2, \ dots, N $. The edges are numbered $ 1, 2, \ dots, M $, and the edge $ i $ connects the vertices $ a_i $ and $ b_i $. Also, the edge $ i $ disappears at time $ t_i $. It takes a unit time to pass through each side. You are initially at vertex 1 at time 0. You want to maximize the score you get by time $ T $ by acting optimally. The score is initially 0 and the event occurs according to:

1. If the current time $ t'$ satisfies $ t'\ geq T $, it ends. If not, go to 2.
2. All edges $ i $ with $ t_i = t'$ disappear.
3. If the vertex you are in is $ v $ and the number of vertices contained in the connected component including the vertex $ v $ is $ x $, $ x $ will be added to the score.
4. You either move to one of the vertices $ v $ and adjacent to it, or stay at vertex $ v $. However, in the former case, the edge that has already disappeared cannot be used.
5. As $ t'\ gets t'+ 1 $, go to 1.



Find the maximum score you can get.



output

Output the maximum score. Also, output a line break at the end.

Example

Input

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


Output

8
#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 55;

int N, M, T;
int x[200000], y[200000], z[200000];
vector< pair< int, int > > g[200000];
int64 v[200000];

struct UnionFind
{
  vector< int64 > data, time, score;

  UnionFind(int sz)
  {
    data.assign(sz, -1LL);
    time.assign(sz, T);
    score.resize(sz);
    for(int i = 0; i < sz; i++) {
      if(v[i] == INF) score[i] = -INF;
      else score[i] = 0;
    }
  }

  int64 find(int64 k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  void unite(int64 x, int64 y, int64 z)
  {
    x = find(x), y = find(y);
    if(x == y) return;
    score[x] = max(score[x] + size(x) * (time[x] - z), score[y] + size(y) * (time[y] - z));
    data[x] += data[y];
    data[y] = x;
    time[x] = z;
  }

  int64 size(int64 k)
  {
    return (-data[find(k)]);
  }

  int64 res()
  {
    return (score[find(0)] + size(0) * time[find(0)]);
  }
};

int main()
{
  cin >> N >> M >> T;
  for(int i = 0; i < M; i++) {
    cin >> x[i] >> y[i] >> z[i];
    --x[i], --y[i];
    g[x[i]].emplace_back(y[i], z[i]);
    g[y[i]].emplace_back(x[i], z[i]);
  }

  fill_n(v, 100000, INF);
  queue< int > que;
  que.push(0);
  v[0] = 0;
  while(!que.empty()) {
    int p = que.front();
    que.pop();
    for(auto &e : g[p]) {
      if(v[e.first] != INF || v[p] >= e.second) continue;
      v[e.first] = v[p] + 1;
      que.emplace(e.first);
    }
  }

  vector< int > to(M);
  iota(begin(to), end(to), 0);
  sort(begin(to), end(to), [&](int a, int b)
  {
    return (z[a] > z[b]);
  });
  UnionFind tree(N);
  for(int i : to) tree.unite(x[i], y[i], z[i]);
  cout << tree.res() << endl;
}