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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 100000

struct Edge{
	Edge(int arg_from,int arg_to,int arg_time){
		from = arg_from;
		to = arg_to;
		time = arg_time;
	}
	bool operator<(const struct Edge &arg) const{ //時刻の降順(PQ)
		return time < arg.time;
	}

	int from,to,time;
};

struct Info{
	Info(int arg_node_id,int arg_sum_dist){
		node_id = arg_node_id;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Info &arg) const{ //総移動距離の昇順(PQ)
		return sum_dist > arg.sum_dist;
	}

	int node_id,sum_dist;
};

struct Data{
	Data(int arg_to,int arg_limit_time){
		to = arg_to;
		limit_time = arg_limit_time;
	}
	int to,limit_time;
};

int N;
int M;
ll T;
int boss[NUM];
ll pre_time[NUM],member_num[NUM];
int min_dist[NUM]; //★時刻0の時点で頂点1にいる!!★
vector<Data> G[NUM];
ll value[NUM];

int get_boss(int id){
	if(id == boss[id])return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

void unite(int x,int y,int unite_time){
	int x_boss_id = get_boss(x);
	int y_boss_id = get_boss(y);

	if(x_boss_id == y_boss_id){ //同じグループ

		value[x_boss_id] += (pre_time[x_boss_id]-unite_time)*member_num[x_boss_id];
		pre_time[x_boss_id] = unite_time;

	}else{ //違うグループ

		if(min_dist[x_boss_id] >= T && min_dist[y_boss_id] >= T){

			//とりあえずxに吸収しておく
			boss[y_boss_id] = x_boss_id;
			member_num[x_boss_id] = member_num[x_boss_id]+member_num[y_boss_id];

		}else if(min_dist[x_boss_id] <= T-1 && min_dist[y_boss_id] >= T){ //x_boss_idのみ、時刻T-1で辿り着ける

			//元々x_boss_idにいたことにする
			boss[y_boss_id] = x_boss_id;
			value[x_boss_id] += (pre_time[x_boss_id]-unite_time)*member_num[x_boss_id];
			pre_time[x_boss_id] = unite_time;
			member_num[x_boss_id] = member_num[x_boss_id]+member_num[y_boss_id];

		}else if(min_dist[x_boss_id] >= T && min_dist[y_boss_id] <= T-1){

			//元々y_boss_idにいたことにする
			boss[x_boss_id] = y_boss_id;
			value[y_boss_id] += (pre_time[y_boss_id]-unite_time)*member_num[y_boss_id];
			pre_time[y_boss_id] = unite_time;
			member_num[y_boss_id] = member_num[x_boss_id]+member_num[y_boss_id];

		}else{ //両方、時刻Tの時点で辿り着ける

			//それぞれのグループの、unite直前でのvalueを計算する
			value[x_boss_id] += (pre_time[x_boss_id]-unite_time)*member_num[x_boss_id];
			value[y_boss_id] += (pre_time[y_boss_id]-unite_time)*member_num[y_boss_id];

			int new_boss_id;
			//これから先辿る未来は同じなので、有利な過去を選ぶ(元々valueが大きなグループにいたことにする)
			if(value[x_boss_id] >= value[y_boss_id]){
				boss[y_boss_id] = x_boss_id;
				new_boss_id = x_boss_id;
			}else{
				boss[x_boss_id] = y_boss_id;
				new_boss_id = y_boss_id;
			}
			pre_time[new_boss_id] = unite_time;
			member_num[new_boss_id] = member_num[x_boss_id]+member_num[y_boss_id];
		}
	}
}

void dijkstra(){
	min_dist[0] = 0;
	for(int i = 1; i < N; i++)min_dist[i] = BIG_NUM;

	priority_queue<Info> Q;
	Q.push(Info(0,0));

	int next_node,next_dist;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().node_id]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){

				next_node = G[Q.top().node_id][i].to;
				next_dist = Q.top().sum_dist+1;

				if(next_dist > G[Q.top().node_id][i].limit_time+1)continue; //★その時間までにエッジが消えていたら行けない★

				if(min_dist[next_node] > next_dist){
					min_dist[next_node] = next_dist;
					Q.push(Info(next_node,next_dist));
				}
			}
			Q.pop();
		}
	}

}

int main(){

	scanf("%d %d %d",&N,&M,&T);

	int from,to,time;
	priority_queue<Edge> Q;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %d",&from,&to,&time);
		from--;
		to--;
		time--; //★timeに消えるので、時間を逆に回すと、time-1に発生する★
		Q.push(Edge(from,to,time));
		G[from].push_back(Data(to,time));
		G[to].push_back(Data(from,time));
	}

	dijkstra();

	int debug = 0;
	for(int i = 0; i < N; i++){
		if(min_dist[i] == BIG_NUM)debug++;
	}

	//情報の初期化
	for(int i = 0; i < N; i++){
		boss[i] = i;
		pre_time[i] = T-1;
		member_num[i] = 1;
		value[i] = 0;
	}

	while(!Q.empty()){ //時間を逆向きに回す(★一度uniteされたら、以後は運命を共にするイメージ★)
		unite(Q.top().from,Q.top().to,Q.top().time);
		Q.pop();
	}

	ll ans = 0;
	int boss_id;

	//最終計算
	for(int i = 0; i < N; i++){
		boss_id = get_boss(i);
		if(boss_id != i)continue; //ボス以外はSKIP
		if(min_dist[boss_id] >= T)continue;//時刻T-1の時点でそのノードにいられないならcontinue
		value[boss_id] += (pre_time[boss_id]-0+1)*member_num[boss_id]; //★最後のみ、現在時刻(0)を含む
		ans = max(ans,value[boss_id]);
	}

	printf("%lld\n",ans);

	return 0;
}

