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;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
LL N,M,T;
int a[212345];
int b[212345];
int c[212345];
int d[212345];
int exist[212345];
typedef vector<int> V;
typedef vector<V> VV;
VV g;
typedef pair<int,int> P;
void dijkstra(){
    priority_queue<P> que;
    que.push(P(0,1));
    d[1]=0;
    while(que.size()){
        int t,v;
        tie(t,v)=que.top();t*=-1;que.pop();
        if(t<=T)exist[v]=1;
        if(d[v]<t)continue;
        for(auto &e:g[v]){
            int u=v^a[e]^b[e];
            int cost=d[v]+1;
            if(cost<=c[e]&&d[u]>cost){
                d[u]=cost;
                que.push(P(-cost,u));
            }
        }
    }
}

namespace _DSU{
    int cnt=0;
    LL mem[5][212345];
    LL *get(){
        return mem[cnt++];
    }
}
int now;
const LL INF=1e12;
struct UnionFind{
    LL *par,*rank,*res,*t,*sz;
    LL find(LL x){
        res[x]+=sz[x]*(t[x]-now);
        t[x]=now;
        if(par[x]==x){
            return x;
        }
        else {
            LL p=find(par[x]);
            sz[p]+=sz[x];sz[x]=0;
            chmax(res[p],res[x]);
            res[x]=-INF;
            return p;
        }
    }
    UnionFind(int n,LL *par,LL *rank,LL* res,LL *t,LL *sz)
        :par(par),rank(rank),res(res),t(t),sz(sz){
        FOR(i,1,n+1){
            par[i]=i,rank[i]=0,sz[i]=1;
            if(exist[i]){
                res[i]=0;
                t[i]=T;
            }
            else{
                t[i]=T;
                res[i]=-INF;
            }
        }
    }
    UnionFind(int n):UnionFind(n,_DSU::get(),_DSU::get(),_DSU::get(),_DSU::get(),_DSU::get()){}
    bool unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return false;
        if(rank[x]>rank[y])swap(x,y);
        //cout<<res[x]<<" "<<res[y]<<endl;
        sz[y]+=sz[x];sz[x]=0;
        chmax(res[y],res[x]);
        res[x]=-INF;
        par[x]=y;
        if(rank[x]==rank[y])rank[y]++;
        //cout<<now<<" "<<res[y]<<" "<<sz[y]<<endl;
        return true;
    }
    
        
};


int main(){
    cin>>N>>M>>T;
    vector<P> p;
    REP(i,N+1)d[i]=114514,exist[i]=0;
    g.resize(N+1);
    REP(i,M){
        cin>>a[i]>>b[i]>>c[i];
        p.pb(make_pair(c[i],i));
        g[a[i]].pb(i);
        g[b[i]].pb(i);
    }
    sort(ALL(p));
    reverse(ALL(p));
    dijkstra();
    UnionFind uf(N);
    REP(i,M){
        int e=p[i].se;
        now=p[i].fi;
        int x=a[e],y=b[e];
        uf.unite(x,y);
    }
    LL res=0;
    FOR(i,1,N+1){
        int id=uf.find(i);
        chmax(res,uf.res[id]+uf.sz[id]*(uf.t[id]));
    }
    cout<<res<<endl;
    return 0;
}