// Author: AquariusZhao #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5, M = 2e5 + 5; int head[N], epos; struct Edge { int u, v, w, nxt; } e[M << 1]; ll k, ans; int W[N], id[N], tot; void addEdge(int u, int v, int w) { // cout << u << ' ' << v << ' ' << w << endl; e[++epos] = {u, v, w, head[u]}; head[u] = epos; } namespace O { int n, m; int head[N], epos = 1; Edge e[M << 1]; void addEdge(int u, int v, int w) { e[++epos] = {u, v, w, head[u]}; head[u] = epos; } int dfncnt, dfn[N], low[N]; bool bridge[N << 1]; void tarjan(int u, int fa) { dfn[u] = low[u] = ++dfncnt; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = true; } else if (v != fa && dfn[v] < dfn[u]) low[u] = min(low[u], dfn[v]); } } bool vis[N]; void dfs(int u) { vis[u] = true; id[u] = tot; W[tot]++; for (int i = head[u]; i; i = e[i].nxt) { if (vis[e[i].v] || bridge[i]) continue; dfs(e[i].v); } } void init() { cin >> n >> m >> k; int u, v, w; for (int i = 1; i <= m; i++) scanf("%d%d%d", &u, &v, &w), addEdge(u, v, w), addEdge(v, u, w); tarjan(1, 0); for (int i = 1; i <= n; i++) if (!vis[i]) { ++tot; dfs(i); } } }; int n; bool vis[N]; int root, sz[N], mx[N]; int pos, tmp[N], belong[N], cnt[N]; ll dis[N]; void get_root(int u, int fa, int Sz) { sz[u] = 1; mx[u] = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (vis[v] || v == fa) continue; get_root(v, u, Sz); sz[u] += sz[v]; mx[u] = max(mx[u], sz[v]); } mx[u] = max(mx[u], Sz - sz[u]); if (!root || mx[u] < mx[root]) root = u; } void get_dis(int u, int fa, int Fa) { tmp[++pos] = u; belong[u] = Fa; cnt[Fa] += W[u]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (vis[v] || v == fa) continue; dis[v] = dis[u] + e[i].w; get_dis(v, u, Fa); } } bool cmp(int x, int y) { return dis[x] < dis[y]; } void cal(int u) { pos = 0; tmp[++pos] = u; dis[u] = 0; belong[u] = u; cnt[u] = W[u]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (vis[v]) continue; cnt[v] = 0; dis[v] = dis[u] + e[i].w; get_dis(v, u, v); } sort(tmp + 1, tmp + pos + 1, cmp); // cout << u << ":" << endl; // for (int i = 1; i <= pos; i++) // printf("%d%c", tmp[i], " \n"[i == pos]); // for (int i = 1; i <= pos; i++) // printf("%lld%c", dis[tmp[i]], " \n"[i == pos]); ll sum = 0; for (int i = 1; i <= pos; i++) sum += W[tmp[i]]; // cout << sum << endl; int r = pos; for (int l = 1; l < r; l++) { // cout << " " << l << endl; cnt[belong[tmp[l]]] -= W[tmp[l]]; sum -= W[tmp[l]]; while (l < r && dis[tmp[l]] + dis[tmp[r]] > k) { cnt[belong[tmp[r]]] -= W[tmp[r]]; sum -= W[tmp[r]]; r--; } // cout << " " << r << ' ' << sum << endl; if (l < r) ans += W[tmp[l]] * (sum - cnt[belong[tmp[l]]]); } // cout << "-------" << ans<< endl; } void solve(int u) { vis[u] = true; cal(u); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (vis[v]) continue; root = 0; get_root(v, 0, sz[v]); solve(root); } } int main() { #ifdef aquazhao freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif O::init(); n = tot; for (int i = 1; i <= O::epos; i++) if (O::bridge[i]) addEdge(id[O::e[i].u], id[O::e[i].v], O::e[i].w); get_root(1, 0, O::n); // cout << root << endl; solve(root); // cout << ans << endl; for (int i = 1; i <= n; i++) ans += 1ll * W[i] * (W[i] - 1) / 2; // for (int i = 1; i <= n; i++) // printf("%d%c", W[i], " \n"[i == n]); cout << ans << endl; return 0; }