#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; }; 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; } #define mk make_pair vector<pii>G; int T[MAXN]; void updt(int u,int lst,int tp){ if(vis[u])return; G.pb(mk(tp,p[u])); for(inx(u))if(v!=lst)updt(v,u,tp+w); } int qry(){ sort(G.begin(),G.end()); // for(auto o:G)cout<<o.fr<<" "<<o.sc<<endl; T[0]=G[0].sc; for(int i=1;i<G.size();i++)T[i]=T[i-1]+G[i].sc; int res=0; for(int i=0,j=G.size()-1;i<G.size();i++){ while(j>=0&&G[j].fr+G[i].fr>k)j--; if(j>=0)res+=G[i].sc*T[j]; } G.clear(); // cout<<res<<endl; return res; } void getans(int u){ G.pb(mk(0,p[u])); for(inx(u))if(!vis[v])updt(v,u,w); ans+=qry(); for(inx(u))if(!vis[v])updt(v,u,w),ans-=qry(); G.pb(mk(0,p[u])); ans-=qry(); } 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);//,cout<<bel[u]<<" "<<bel[v]<<" "<<w<<endl; } for(int i=1;i<=t;i++)ans+=p[i]*(p[i]-1);//,cout<<p[i]<<" ";cout<<endl; siz[1]=t; dfz(1); printf("%lld",ans/2); } signed main(){ slv(); return 0; }