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 int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001;
int N,M,T;

int dist[111111];

struct UF{
    vint par,sz,pre,ma;
    UF(int n){
        par.resize(n);
        sz.resize(n);
        pre.resize(n);
        ma.resize(n);
        rep(i,n){
            par[i]=i;
            sz[i]=1;
            pre[i]=T;
            if(dist[i]==INF)ma[i]=-INF;
            else ma[i]=0;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y,int t){
        x=find(x);y=find(y);
        if(x==y)return;

        int a=(pre[x]-t)*sz[x]+ma[x];
        int b=(pre[y]-t)*sz[y]+ma[y];

        ma[x]=max(a,b);
        sz[x]+=sz[y];
        par[y]=x;
        pre[x]=t;
    }

    int latte(){
        int x=find(0);
        return ma[x]+pre[x]*sz[x];
    }
};

vector<pint>G[111111];

signed main(){
    scanf("%lld%lld%lld",&N,&M,&T);

    vector<tuple<int,int,int>>es;
    rep(i,M){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        a--;b--;
        G[a].pb({b,c});
        G[b].pb({a,c});
        es.pb(make_tuple(c,a,b));
    }
    sort(all(es));reverse(all(es));


    fill_n(dist,111111,INF);
    dist[0]=0;
    queue<int>que;
    que.push(0);
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto &e:G[v]){
            if(dist[e.fi]!=INF||dist[v]>=e.se)continue;
            dist[e.fi]=dist[v]+1;
            que.push(e.fi);
        }
    }



    UF uf(N);
    for(auto &w:es){
        int t,a,b;
        tie(t,a,b)=w;
        uf.unite(a,b,t);
    }

    printf("%lld\n",uf.latte());
}