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 <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include <set>

class UnionFind {
	std::vector<int> vec;
public:
	UnionFind(int size) : vec(size, -1) {};
	int find(int a) {
		return vec[a] < 0 ? a : vec[a] = find(vec[a]);
	}
	bool same(int a, int b) {
		return find(a) == find(b);
	}
	int size_of(int a) {
		return -vec[find(a)];
	}
	void unite(int a, int b) {
		a = find(a); b = find(b);
		if (a != b) {
			if (vec[a] > vec[b]) std::swap(a, b);
			vec[a] += vec[b];
			vec[b] = a;
		}
	}
};
struct Bridge {
	int to, time;
};
struct Bidirect {
	int a, b, time;
};
int main() {
	int n, m, t; std::cin >> n >> m >> t;
	std::vector<Bidirect> bridges(m);
	std::vector<std::vector<Bridge>> islands(n);
	for (auto& bridge : bridges) {
		std::cin >> bridge.a >> bridge.b >> bridge.time;
		--bridge.a; --bridge.b;
		islands[bridge.a].push_back(Bridge{ bridge.b, bridge.time });
		islands[bridge.b].push_back(Bridge{ bridge.a, bridge.time });
	}
	std::vector<int> depth(n, INT_MAX); depth[0] = 0;
	std::queue<int> queue; queue.push(0);
	while (!queue.empty()) {
		const auto top = queue.front(); queue.pop();
		for (const auto bridge : islands[top]) if (bridge.time > depth[top] && depth[bridge.to] == INT_MAX) {
			depth[bridge.to] = depth[top] + 1;
			queue.push(bridge.to);
		}
	}
	std::vector<long long int> sum_score(n, 0);
	std::vector<int> last_changed(n, t), max_position(n); std::iota(max_position.begin(), max_position.end(), 0);
	std::sort(bridges.rbegin(), bridges.rend(), [](const Bidirect a, const Bidirect b) {return a.time < b.time; });
	UnionFind uft(n);
	for (const auto bridge : bridges) {
		if (uft.same(bridge.a, bridge.b)) continue;
		const auto a_max = max_position[uft.find(bridge.a)];
		const auto b_max = max_position[uft.find(bridge.b)];
		const long long int a_max_size = uft.size_of(bridge.a);
		const long long int b_max_size = uft.size_of(bridge.b);
		sum_score[a_max] += a_max_size * (last_changed[a_max] - bridge.time);
		sum_score[b_max] += b_max_size * (last_changed[b_max] - bridge.time);
		if (depth[a_max] > t) sum_score[a_max] = 0;
		if (depth[b_max] > t) sum_score[b_max] = 0;
		uft.unite(bridge.a, bridge.b);
		const auto new_root = uft.find(bridge.a);
		if (sum_score[a_max] > sum_score[b_max]) {
			max_position[new_root] = a_max;
			last_changed[a_max] = bridge.time;
		}
		else {
			max_position[new_root] = b_max;
			last_changed[b_max] = bridge.time;
		}
	}
	for (auto i = 0; i < n; ++i) {
		const auto max = max_position[uft.find(i)];
		sum_score[max] += uft.size_of(max) * (last_changed[max] - 0LL);
		if (depth[max] > t) sum_score[max] = 0;
		last_changed[max] = 0;
	}
	std::cout << *std::max_element(sum_score.begin(), sum_score.end()) << std::endl;
}

