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 <iostream>
#include <vector>
#include <queue>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
const int INF = 1145141919;

struct union_find {
	vector<int> v;
	union_find(int n) : v(n, -1) {}
	int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		if (-v[x] < -v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
	}
	bool root(int x) { return v[x] < 0; }
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -v[find(x)]; }
};

int T;

void dfs(int u, int t0, ll x, vector<vector<i_i> >& chs, vector<int>& sz, vector<ll>& ans) {
	for (i_i p: chs[u]) {
		int v = p.first, t = p.second;
		ans[u] = x + (ll)(t - t0) * sz[u];
		dfs(v, t, ans[u], chs, sz, ans);
	}
	ans[u] = x + (ll)(T - 1 - t0) * sz[u];
}

int main() {
	int N, M; cin >> N >> M >> T;
	vector<int> a(M), b(M), t(M);
	rep(i, M) {
		scanf("%d%d%d", &a[i], &b[i], &t[i]);
		a[i]--; b[i]--; t[i]--;
	}
	vector<vector<i_i> > G(N);
	rep(i, M) {
		G[a[i]].pb(i_i(b[i], t[i]));
		G[b[i]].pb(i_i(a[i], t[i]));
	}
	vector<int> d(N, INF); d[0] = 0;
	queue<int> q; q.push(0);
	while (q.size()) {
		int u = q.front(); q.pop();
		for (i_i p: G[u]) {
			int v = p.first, t = p.second;
			if (d[u] <= t && d[u] + 1 < d[v]) {
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	vector<vector<int> > unko(T);
	rep(i, M) unko[t[i]].pb(i);
	union_find uf(N);
	int K = N;
	vector<int> index(N);
	rep(u, N) index[u] = u;
	vector<vector<i_i> > chs(N * 2 - 1);
	vector<int> sz(N * 2 - 1);
	rep(u, N) sz[u] = 1;
	for (int t = T - 1; t >= 0; t--)
		for (int i: unko[t]) {
			if (uf.same(a[i], b[i])) continue;
			int x = index[uf.find(a[i])], y = index[uf.find(b[i])];
			uf.unite(a[i], b[i]);
			int z = (index[uf.find(a[i])] = K++);
			chs[z].pb(i_i(x, t)); chs[z].pb(i_i(y, t));
			sz[z] = uf.size(a[i]);
		}
	vector<ll> ans(N * 2 - 1);
	dfs(N * 2 - 2, -1, 0, chs, sz, ans);
	ll ma = 0;
	rep(u, N) if (d[u] < INF) ma = max(ma, ans[u]);
	cout << ma << endl;
	// rep(u, N) cout << ans[u] << ' ';
	// cout << endl;
}