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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

const int MN=100010;
typedef long long ll;
struct unionfind{
	int par[MN];
	int sz[MN];
	int prevt[MN];
	ll sco[MN];
	void init(int N){rep(i,N) par[i]=i,prevt[i]=0,sco[i]=0,sz[i]=1;}
	int find(int x){
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y,int t){
		x=find(x),y=find(y);
		if(x==y) return;
		ll nsco = max(sco[x]+(ll)(t-prevt[x])*sz[x], sco[y]+(ll)(t-prevt[y])*sz[y]);
		int nsz = sz[x]+sz[y];
		int nt = t;

		par[y]=x;
		sco[x]=nsco;
		sz[x]=nsz;
		prevt[x]=nt;
	}
}UF;

typedef pair<int,int> P;
vector<P> G[MN];
int d[MN];
int inf = 1e8;
int N,M,T;
void dijkstra(){
	priority_queue<P,vector<P>,greater<P> > que;
	rep(i,N) d[i]=inf;
	d[0]=0;
	que.push(P(0,0));
	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v = p.sc;
		int c = p.fs;
		if(d[v]!=c) continue;
		for(P p:G[v]){
			int to = p.fs;
			if(p.sc<=d[v]) continue;
			if(d[to]>d[v]+1){
				d[to]=d[v]+1;
				que.push(P(d[to],to));
			}
		}
	}
}

vector<P> es[100010];

int main(){
	cin>>N>>M>>T;
	rep(i,M){
		int a,b,t;
		cin>>a>>b>>t;
		a--,b--;
		G[a].pb(P(b,t));
		G[b].pb(P(a,t));
		es[T-t].pb(P(a,b));
	}
	dijkstra();
//	rep(i,N) show(d[i]);

	UF.init(N);
	rep(i,N) if(d[i]==inf) UF.sco[i] = -1e18;
	rep(t,T){
		for(P e:es[t]){
			int a = e.fs,b=e.sc;
			if(UF.same(a,b)) continue;
			UF.unite(a,b,t);
		}
	}
	int r = UF.find(0);
	ll ans = UF.sco[r] + (ll)(T-UF.prevt[r])*N;
	cout<<ans<<endl;
}