#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define pb push_back #define lson t[pos].ls #define rson t[pos].rs #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,inf=300000000000000; struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT=1;void add_side(int u,int v,int w){edge[++CNT]={v,h[u],w};h[u]=CNT;edge[++CNT]={u,h[v],w};h[v]=CNT;} int n,m,k,t,low[MAXN],dfn[MAXN],cnt,bel[MAXN],p[MAXN]; stack<int>st; void dfs(int u,int lst){ dfn[u]=low[u]=++cnt; st.push(u); for(inx(u))if(I!=lst){ if(dfn[v]){ low[u]=min(low[u],dfn[v]); } else{ dfs(v,I^1); low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){t++; while(st.top()!=u)bel[st.top()]=t,st.pop(),p[t]++; bel[st.top()]=t,st.pop(),p[t]++; } } struct side{int u,v,w;}s[MAXN]; bool vis[MAXN]; int siz[MAXN]; struct node{ int ls,rs,x; }; struct treearray{ node t[MAXN*33]; int tot,rt; void pushup(int pos){ t[pos].x=t[lson].x+t[rson].x; } void update(int &pos,int l,int r,int x,int y){ if(!pos)pos=++tot; if(l==r){ t[pos].x+=y; return; } int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x,y); else update(rson,mid+1,r,x,y); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(!pos)return 0; if(ql<=l&&qr>=r)return t[pos].x; int mid=(l+r)>>1,res=0; if(ql<=mid)res+=query(lson,l,mid,ql,qr); if(qr>mid)res+=query(rson,mid+1,r,ql,qr); return res; } void upd(int x,int y){ update(rt,0,inf,x,y); } int qry(int x){ if(x<0)return 0; return query(rt,0,inf,0,x); } }T; int zx,Mx,sz,ans; void getzx(int u,int lst){ if(vis[u])return; int mx=0;siz[u]=1; for(inx(u))if(v!=lst){ getzx(v,u); siz[u]+=siz[v]; mx=max(mx,siz[v]); } mx=max(mx,sz-siz[u]); if(mx<Mx)Mx=mx,zx=u; } void qry(int u,int lst,int tp){ if(vis[u])return; ans+=T.qry(k-tp)*p[u]; for(inx(u))if(v!=lst)qry(v,u,tp+w); } void updt(int u,int lst,int tp,int y){ if(vis[u])return; T.upd(tp,p[u]*y); for(inx(u))if(v!=lst)updt(v,u,tp+w,y); } void getans(int u){ T.upd(0,p[u]); for(inx(u))if(!vis[v]){ qry(v,u,w); updt(v,u,w,1); } for(inx(u))if(!vis[v]){ updt(v,u,w,-1); } T.upd(0,-p[u]); } void dfz(int u){ Mx=inf,sz=siz[u]; getzx(u,0); getans(zx); vis[zx]=1; int tmp=zx; for(inx(tmp))if(!vis[v])dfz(v); } void slv(){ n=read(),m=read(),k=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); add_side(u,v,w); s[i]={u,v,w}; } dfs(1,0); memset(h,0,sizeof(h)),CNT=1; for(int i=1;i<=m;i++){ int u=s[i].u,v=s[i].v,w=s[i].w; if(bel[u]!=bel[v])add_side(bel[u],bel[v],w); } for(int i=1;i<=t;i++)ans+=p[i]*(p[i]-1)/2; siz[1]=t; dfz(1); printf("%lld",ans); } signed main(){ slv(); return 0; }