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;
const ll MOD = 1e9 + 7;
using PII = pair<ll, ll>;
using PP = pair<ll, PII>;
#define FOR(i,a,n) for(ll i=(ll)a; i<(ll)n; ++i)
#define REP(i,n) FOR(i,0,n)
const ll INF = 1LL << 60;
template<typename T> void chmin(T &a, T b) { a = min(a, b); }
vector<PII> G[300000];
int cnt[300000];
int dist[300000];
struct UnionFind {
	vector<int> par;
	vector<int> rank;
	vector<int> cnt;
	UnionFind(int n) {
		par.resize(n);
		for (int i = 0; i < n; i++) par[i] = i;
		rank.resize(n);
		cnt.resize(n);
	}
	int find(int x) {
		if (x == par[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) {
		x = find(x);
		y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y]) {
			par[x] = y;
			cnt[y] += cnt[x];
		}
		else {
			par[y] = x;
			cnt[x] += cnt[y];
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
};
int main() {
	int N, M, T;
	cin >> N >> M >> T;
	vector<PP> edge;
	for (int i = 0; i < M; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		a--; b--;
		edge.emplace_back(t, PII(a, b));
		G[a].emplace_back(b, t);
		G[b].emplace_back(a, t);
	}
	queue<int> Q;
	fill((int*)dist, (int*)(dist + N), 1 << 30);
	dist[0] = -1;
	Q.push(0);
	while (!Q.empty()) {
		int v = Q.front(); Q.pop();
		for (PII e : G[v]) {
			int to = e.first;
			if (dist[to] == 1 << 30 && dist[v] < e.second - 1) {
				dist[to] = dist[v] + 1;
				Q.push(to);
			}
		}
	}
	sort(edge.begin(), edge.end(), greater<PP>());
	UnionFind U(N + M);
	vector<ll> score(N + M);
	vector<ll> tim(N + M);
	for (int i = 0; i < N; i++) U.cnt[i] = 1;
	for (int i = 0; i < N; i++) {
		if (dist[i] == 1 << 30) {
			score[i] = -(1LL << 60);
		}
		tim[i] = T;
	}
	int k = N;
	for (int i = 0; i < M; i++) {
		int s = edge[i].second.first;
		int t = edge[i].second.second;
		if (U.same(s, t)) continue;
		s = U.find(s);
		t = U.find(t);
		ll ss = max(score[s] + (tim[s] - edge[i].first)*U.cnt[s], score[t] + (tim[t] - edge[i].first)*U.cnt[t]);
		U.unite(k, s);
		U.unite(k, t);
		tim[U.find(k)] = edge[i].first;
		score[U.find(k)] = ss;
		k++;
	}
	cout << score[U.find(k - 1)] + N*tim[U.find(k - 1)] << endl;
}
