#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9; struct node { int v, w, id; }; vector<node> G[N]; struct Node { int v, w; }; vector<Node> g[N]; int n, m, C, bel[N], siz[N]; ll K, ans; namespace init { int dfn[N], low[N], cut[N]; void dfs(int u, int fa) { dfn[u] = low[u] = ++dfn[0]; for (auto e : G[u]) { int v = e.v, id = e.id; if (v == fa) continue; if (!dfn[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) cut[id] = 1; } else { low[u] = min(low[u], dfn[v]); } } } void dfs1(int u, int fa) { bel[u] = C, siz[C]++; for (auto e : G[u]) { int v = e.v, id = e.id; if (v == fa || cut[id]) continue; if (!bel[v]) dfs1(v, u); } } void Main() { dfs(1, 0); for (int i = 1; i <= n; i++) { if (!bel[i]) C++, dfs1(i, 0); } for (int i = 1; i <= n; i++) { for (auto e : G[i]) { int j = e.v, w = e.w; if (bel[i] != bel[j]) { g[bel[i]].push_back({bel[j], w}); } } } } } struct NODE { int ls, rs, siz, cnt, rnd; ll val; NODE(ll v = 0, int w = 0) : ls(0), rs(0), val(v), siz(w), cnt(w), rnd(rand()) {} } t[N]; struct Treap { int rt, tot; void clear() {rt = tot = 0;} void pu(int u) { t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + t[u].cnt; } void split(int u, ll k, int &x, int &y) { if (!u) {x = y = 0; return;} if (t[u].val <= k) { x = u, split(t[u].rs, k, t[u].rs, y); } else { y = u, split(t[u].ls, k, x, t[u].ls); } pu(u); } int merge(int x, int y) { if (!x || !y) return x | y; if (t[x].rnd < t[y].rnd) { t[x].rs = merge(t[x].rs, y); pu(x); return x; } else { t[y].ls = merge(x, t[y].ls); pu(y); return y; } } void ins(ll v, int w) { int x, y, z; split(rt, v - 1, x, y), split(y, v, y, z); if (!y) y = ++tot, t[tot] = NODE(v, w); else t[y].siz += w, t[y].cnt += w; rt = merge(merge(x, y), z); } int rnk(ll v) { int x, y; split(rt, v, x, y); int res = t[x].siz; rt = merge(x, y); return res; } } T; bool vis[N]; namespace Find { int Siz[N], mxsiz[N]; void dfs(int u, int fa) { Siz[u] = 1, mxsiz[u] = 0; for (auto e : g[u]) { int v = e.v; if (v == fa || vis[v]) continue; dfs(v, u), Siz[u] += Siz[v]; mxsiz[u] = max(mxsiz[u], Siz[v]); } mxsiz[u] = max(mxsiz[u], C - Siz[u]); } int get(int u) { dfs(u, 0); for (int i = 1; i <= C; i++) { if (mxsiz[i] <= C / 2) return i; } } } int Siz[N], mxsiz[N], subT[N], tp, cen[N]; ll dis[N]; void dfs(int u, int fa) { Siz[u] = 1, mxsiz[u] = 0, subT[++tp] = u; for (auto e : g[u]) { int v = e.v, w = e.w; if (v == fa || vis[v]) continue; dis[v] = dis[u] + w; dfs(v, u), Siz[u] += Siz[v]; mxsiz[u] = max(mxsiz[u], Siz[v]); } } void dfs(int u) { vis[u] = 1; T.clear(); for (auto e : g[u]) { int v = e.v, w = e.w; if (vis[v]) continue; dis[v] = w, tp = 0, dfs(v, u); for (int i = 1; i <= tp; i++) { int U = subT[i]; mxsiz[U] = max(mxsiz[U], Siz[v] - Siz[U]); if (mxsiz[U] <= Siz[v] / 2) cen[v] = U; ans += 1ll * T.rnk(K - dis[U]) * siz[U]; if (K >= dis[U]) ans += siz[U] * siz[u]; } for (int i = 1; i <= tp; i++) { int U = subT[i]; T.ins(dis[U], siz[U]); } } for (auto e : g[u]) if (!vis[e.v]) dfs(cen[e.v]); } signed main() { srand(time(0)); scanf("%d%d%lld", &n, &m, &K); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].push_back({v, w, i}); G[v].push_back({u, w, i}); } init::Main(); for (int i = 1; i <= C; i++) ans += 1ll * siz[i] * (siz[i] - 1) / 2; dfs(Find::get(1)); printf("%lld\n", ans); return 0; }