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;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__",", __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600

class UnionFind {
public:
  vector<int> par, rank; // parent(negative := its root and abs-value is its size), depth
  UnionFind(int sz) : par(sz, -1), rank(sz, 0){}
  int find(int x){
    if(par[x]<0) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y){
    x=find(x); y=find(y);
    if(x==y) return;  // already belong to same tree
    if(rank[x] < rank[y]){  // y becomes parent node
      par[y] += par[x];
      par[x] = y;
    } else {  // x becomes parent node
      par[x] += par[y];
      par[y] = x;
      if(rank[x]==rank[y]) rank[x]++;
    }
  }
  bool same(int x, int y){ return find(x) == find(y); }
  int size(int x){ return -par[find(x)]; }
};

int main(){
  int n,m,T;
  cin>>n>>m>>T;
  vector<vector<pair<int,int>>> vec(n);
  vector<pair<int,pair<int,int>>> edge(m);
  rep(i,m){
    int a,b,t;
    cin>>a>>b>>t;
    a--;b--;
    vec[a].pb(mp(b,t));
    vec[b].pb(mp(a,t));
    edge[i] = mp(t,mp(a,b));
  }

  vector<int> d(n,INF);
  d[0]=0;
  queue<int> q;
  q.push(0);
  while(!q.empty()){
    int v = q.front(); q.pop();
    int dis = d[v];
    for(auto to : vec[v]){
      if(to.se <= dis) continue;
      if(d[to.fi] <= dis+1) continue;
      d[to.first] = dis+1;
      q.push(to.first);
    }
  }

  sort(all(edge)); reverse(all(edge));
  UnionFind uf(n);

  vector<long> maxval(n,0), lastvisit(n,T);
  rep(i,n) if(d[i]<INF) maxval[i]=1;

  auto getlazy = [&](int x, int t){
    int node = uf.find(x);
    if(maxval[node]==0) return 0L;
    else if(lastvisit[node]==t) return maxval[node];
    else {
      long add = (lastvisit[node]-t)*uf.size(x);
      return maxval[node] + add;
    }
  };

  rep(i,m){
    int u = edge[i].se.fi, v = edge[i].se.se;
    int t = edge[i].fi;
    if(uf.same(u,v)) continue;
    else if(t==T){
      bool visitable = true;
      if(maxval[uf.find(u)] == 0 && maxval[uf.find(v)]==0) visitable=false;
      uf.unite(u,v);
      if(visitable) maxval[uf.find(u)] = uf.size(u);
    }
    else {
      long lu = getlazy(u, t), lv = getlazy(v, t);
      if(lu==0 && lv==0){ uf.unite(u,v); continue; }
      if(lu>0) lu += uf.size(v);
      if(lv>0) lv += uf.size(u);
      uf.unite(u,v);
      maxval[uf.find(u)] = max<long>(lu,lv);
      lastvisit[uf.find(u)] = t; //dbg(uf.find(u), maxval[uf.find(u)]);
    }
  }

  cout << getlazy(0, 1) << endl;
  assert(getlazy(0,1)>0);

  return 0;
}