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 <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }


int rand_int(int a, int b) {
    static random_device rd;
    static mt19937 gen(rd());
    return uniform_int_distribution<int>(a, b)(gen);
}


struct UnionFind {
    V<int> id;
    V<int> data;
    VV<int> groups;
    UnionFind(int n) {
        id = V<int>(n);
        data = V<int>(n);
        groups = VV<int>(n);
        for (int i = 0; i < n; i++) {
            id[i] = i;
            groups[i].push_back(i);
        }
    }
    void setd(int a, int x) {
        data[id[a]] = x;
        return;
    }
    int getd(int a) {
        return data[id[a]];
    }

    bool same(int a, int b) {
        return id[a] == id[b];
    }
    void merge(int a, int b) {
        if (same(a, b)) return;
        int x = id[a], y = id[b];
        if (groups[x].size() < groups[y].size()) swap(x, y);
        for (int d: groups[y]) {
            id[d] = x;
            groups[x].push_back(d);
        }
        groups[y].clear();
    }
};
using P = pair<int, int>;
const int MN = 300300;
V<P> ed[MN];

int n;
P vs[MN]; //start, size
V<int> g[MN];
ll pnt[MN];

void dfs(int p, int nw, ll sm) {
//    cout << p << endl;
    sm += ll(vs[p].first-nw)*vs[p].second;
    if (p < n) {
//        cout << "last " << p << " " << sm << endl;
        pnt[p] = sm;
        return;
    }
    for (int d: g[p]) {
        dfs(d, vs[p].first, sm);
    }
}

V<P> gg[MN]; //to, time

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
    int m, t;
    cin >> n >> m >> t;
    for (int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t; a--; b--; t--;
        ed[t].push_back(P(a, b));
        gg[a].push_back(P(b, t));
        gg[b].push_back(P(a, t));
    }
    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
        vs[i] = P(t, 1);
        uf.setd(i, i);
    }
    int vc = n;
    for (int i = t-1; i >= 0; i--) {
        for (auto p: ed[i]) {
            int a, b;
            tie(a, b) = p;
            if (uf.same(a, b)) continue;
            int ad = uf.getd(a);
            int bd = uf.getd(b);
            uf.merge(a, b);
            int vid = vc; vc++;
            vs[vid] = P(i+1, vs[ad].second + vs[bd].second);
            g[vid].push_back(ad);
            g[vid].push_back(bd);
            uf.setd(a, vid);
        }
    }
    dfs(vc-1, 0, 0);

    ll ans = 0;
    queue<P> que;
    V<bool> used(n);
    que.push(P(0, 0));
    while (!que.empty()) {
        P p = que.front(); que.pop();
        int a, tm;
        tie(a, tm) = p; 
        if (used[a]) continue;
        used[a] = true;
        ans = max(ans, pnt[a]);
        for (auto ed: gg[a]) {
            if (ed.second < tm) continue;
            que.push(P(ed.first, tm+1));
        }
    }

    cout << ans << endl;
    return 0;
}