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;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const int INF = 1e9;

class UnionFind{
private:
  vector<int> par, rank;
public:
  VI sz, dd;
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	sz.assign(n, 1);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
	int tmp = sz[x] + sz[y];
	sz[x] = sz[y] = tmp;
	dd[x] = dd[y] = min(dd[x], dd[y]);
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  LL N, M, T;
  cin >> N >> M >> T;
  vector<vector<PII>> es(T+1);
  vector<vector<PII>> G(N);
  REP(i,M){
	int a, b, t;
	cin >> a >> b >> t;
	--a;
	--b;
	es[t].EB(a,b);
	G[a].EB(b,t);
	G[b].EB(a,t);
  }
  VI dist(N, INF);
  dist[0] = 0;
  queue<int> q;
  q.push(0);
  while(!q.empty()){
	int u = q.front();
	q.pop();
	for(auto&& e: G[u]){
	  if(dist[e.FF] == INF && dist[u] < e.SS){
		dist[e.FF] = dist[u] + 1;
		q.push(e.FF);
	  }
	}
  }

  UnionFind uf(N);
  uf.dd = dist;
  VL prv(N, T);
  for(auto&& e: es[T]){
	uf.unite(e.FF, e.SS);
  }

  VL ans(N, 0);
  for(int t=T-1;t>0;--t){
	map<PII,LL> buf;
	for(auto&& e: es[t]){
	  if(uf.same(e.FF, e.SS)) continue;
	  int r1 = uf.find(e.FF);
	  int r2 = uf.find(e.SS);
	  LL s1 = uf.sz[r1];
	  LL s2 = uf.sz[r2];
	  buf[e] = max((ans[r1] + (prv[r1] - t)*s1) * (uf.dd[r1] <= t),
				   ans[r2] + (prv[r2] - t)*s2 * (uf.dd[r2] <= t));
	}

	for(auto&& p: buf){
	  auto& e = p.FF;
	  uf.unite(e.FF, e.SS);
	  int r = uf.find(e.FF);
	  maxi(ans[r], p.SS);
	  prv[r] = t;
	}
  }

  int rt = uf.find(0);
  cout << ans[rt] + prv[rt] * N << endl;

  return 0;
}