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 ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

int n,m,T;
vector<pii> g[125252];
pair<int,pii> es[252521];
bool reachable[125252];

int data[125252];
int lastmerged[125252];
ll score[125252];
int root(int x){
  return data[x]<0?x:data[x]=root(data[x]);
}
void unite(int a,int b,int t){
  a=root(a);
  b=root(b);
  if(a!=b){
    if(data[a]>data[b])swap(a,b);
    if(score[a]>=0){
      int spent = lastmerged[a] - t;
      score[a] += (ll)spent * (-data[a]);
    }
    if(score[b]>=0){
      int spent = lastmerged[b] - t;
      score[b] += (ll)spent * (-data[b]);
    }
    data[a] += data[b];
    data[b] = a;
    CHMAX(score[a], score[b]);
    lastmerged[a] = t;
  }
}

int main(){
  scanf("%d%d%d",&n,&m,&T);
  REP(i,m){
    int a,b,t;
    scanf("%d%d%d",&a,&b,&t);
    --a;--b;
    g[a].push_back(pii(b,t));
    g[b].push_back(pii(a,t));
    es[i] = make_pair(t,pii(a,b));
  }
  reachable[0] = true;
  queue<pii> Q;
  Q.push(pii(0,0));
  while(!Q.empty()){
    pii P = Q.front(); Q.pop();
    int pos = P.first;
    int t = P.second;
    for(pii R : g[pos]){
      int to = R.first;
      int lost = R.second;
      if(lost<=t)continue;
      if(reachable[to])continue;
      reachable[to] = true;
      Q.push(pii(to,t+1));
    }
  }

  REP(i,n)data[i]=-1;
  REP(i,n){
    lastmerged[i] = T;
    if(reachable[i]){
      score[i] = 0;
    }else{
      score[i] = -2521830;
    }
  }
  sort(es,es+m);
  FORR(i,0,m){
    int a = es[i].second.first;
    int b = es[i].second.second;
    unite(a,b,es[i].first);
  }
  ll ans = score[root(0)] + (ll)n * lastmerged[root(0)];
  printf("%lld\n",ans);
  return 0;
}