#include<bits/stdc++.h> #define pii pair<int,int> #define mk make_pair #define fi first #define se second using namespace std; const int N=2e5+10; vector<int> E[N]; int dfn[N],low[N]; int bel[N],dc=0,bc=0; stack<int> s;bool in_s[N]; struct edge{ int u,v,w; }eg[N];int sz[N]; void tj(int u,int fa){ ++dc;dfn[u]=dc,low[u]=dc; s.push(u);in_s[u]=1; for(auto v:E[u]){ if(v==fa) continue; if(!dfn[v]){ tj(v,u);low[u]=min(low[u],low[v]); }else if(in_s[v]){ low[u]=min(low[u],dfn[v]); } }if(dfn[u]==low[u]){ bc++; while(!s.empty()){ int p=s.top();s.pop(); bel[p]=bc;in_s[p]=0;sz[bc]++; if(p==u) break; } } }int n,m; vector<pii> G[N]; long long d[N][22];int fa[N][22]; int dep[N]; void dfs(int u){ //cout<<u<<endl; dep[u]=dep[fa[u][0]]+1; for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(v==fa[u][0]) continue; fa[v][0]=u;d[v][0]=w; for(int i=1;i<=19;i++) fa[v][i]=fa[fa[v][i-1]][i-1],d[v][i]=d[v][i-1]+d[fa[v][i-1]][i-1]; dfs(v); } }long long dis(int a,int b){ long long res=0; if(dep[a]<dep[b]) swap(a,b); for(int i=19;i>=0;i--){ if(dep[fa[a][i]]>=dep[b]){ res+=d[a][i];a=fa[a][i]; } }if(a==b) return res; for(int i=19;i>=0;i--){ if(fa[a][i]!=fa[b][i]){ res+=d[a][i]+d[b][i];a=fa[a][i],b=fa[b][i]; } }return res+d[a][0]+d[b][0]; }long long K; bool vis[N]; int f[N]; int siz[N]; pii mn; void getz(int u,int fa){ siz[u]=1;f[u]=0; for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(v==fa||vis[v]) continue; getz(v,u); siz[u]+=siz[v]; f[u]=max(f[u],siz[v]); } }void getz2(int u,int fa,int rt){ mn=min(mn,mk(max(f[u],siz[rt]-siz[u]),u)); for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(v==fa||vis[v]) continue; getz2(v,u,rt); } }long long ans=0; struct segtree{ #define mid (l+r)/2 int T[N<<5],lc[N<<5],rc[N<<5]; int tot=1; void clear(){ while(tot>=1){ T[tot]=0;lc[tot]=0;rc[tot]=0; tot--; }tot=1; }void pu(int p){ T[p]=0; if(lc[p]) T[p]+=T[lc[p]]; if(rc[p]) T[p]+=T[rc[p]]; }void upd(int p,long long l,long long r,long long x,int v){ if(l==r){ T[p]+=v;return; }if(x<=mid){ if(!lc[p]) lc[p]=++tot; upd(lc[p],l,mid,x,v); }else{ if(!rc[p]) rc[p]=++tot; upd(rc[p],mid+1,r,x,v); }pu(p); //cout<<l<<' '<<r<<' '<<x<<' '<<v<<' '<<T[p]<<endl; }int qry(int p,long long l,long long r,long long pl,long long pr){ if(!p) return 0; if(pl<=l&&r<=pr) return T[p]; int res=0; if(pl<=mid) res+=qry(lc[p],l,mid,pl,pr); if(pr>mid) res+=qry(rc[p],mid+1,r,pl,pr); return res; } }sgt;long long LM=2e14+10; void dfstre(int u,int fa,long long d){ if(K-d>=0) ans+=1ll*sz[u]*sgt.qry(1,0,LM,0,K-d)/*,cout<<K-d<<' '<<sgt.qry(1,0,LM,0,K-d)<<endl*/; for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(v==fa||vis[v]) continue; dfstre(v,u,d+w); } }void dfstre2(int u,int fa,long long d){ sgt.upd(1,0,LM,d,sz[u]); //cout<<u<<' '<<d<<' '<<sz[u]<<endl; for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(v==fa||vis[v]) continue; dfstre2(v,u,d+w); } } void divide(int u){ if(!u) return ; //cout<<u<<' '; vis[u]=1; sgt.clear(); sgt.upd(1,0,LM,0,sz[u]); //cout<<u<<' '; for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(vis[v]) continue; //cout<<"now in "<<u<<",calc "<<v<<". ans change:"; //cout<<ans<<"->"; dfstre(v,u,w); //cout<<ans<<endl; dfstre2(v,u,w); }for(auto ed:G[u]){ int v=ed.fi,w=ed.se; if(vis[v]) continue; mn=mk(1e9,0); getz(v,u);getz2(v,u,v); divide(mn.se); } } int main(){ cin>>n>>m>>K; for(int i=1;i<=m;i++){ int u,v,w;cin>>u>>v>>w; E[u].push_back(v);E[v].push_back(u); eg[i]=(edge){u,v,w}; }for(int i=1;i<=n;i++) if(!dfn[i]) tj(i,0); //for(int i=1;i<=n;i++) cout<<bel[i]<<' ';cout<<endl; // //for(int i=1;i<=n;i++) bel[i]=i; // for(int i=1;i<=m;i++){ int u=bel[eg[i].u]; int v=bel[eg[i].v]; int w=eg[i].w; if(u==v) continue; G[u].push_back(mk(v,w)); G[v].push_back(mk(u,w)); }dfs(1); mn=mk(1e9,0); getz(1,0);getz2(1,0,1); divide(mn.se); for(int i=1;i<=bc;i++) ans+=1ll*(sz[i])*(sz[i]-1)/2; cout<<ans; return 0; }