#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,N;ll k; vector<pi>v[maxn]; vector<pi>G[maxn]; int dfn[maxn],low[maxn],ct; int cnt[maxn]; ll t[maxn]; set<pi>mark; int bel[maxn]; void dfs(int u,int fa){ dfn[u]=low[u]=++ct; for(auto it:v[u]){ if(it.p1==fa)continue; if(dfn[it.p1]){low[u]=min(low[u],dfn[it.p1]);continue;} dfs(it.p1,u);low[u]=min(low[u],low[it.p1]); if(low[it.p1]>dfn[u])t[dfn[it.p1]]+=it.p2,t[ct+1]-=it.p2; } } void sub1(){ ll res=0; up(i,1,n){ up(j,1,n)dfn[j]=low[j]=t[j]=0;ct=0; dfs(i,0); up(j,1,n)t[j]+=t[j-1]; up(j,i+1,n)if(t[dfn[j]]<=k)res++; }cout<<res; } void dfs1(int u,int fa){ dfn[u]=low[u]=++ct; for(auto it:v[u]){ if(it.p1==fa)continue; if(dfn[it.p1]){low[u]=min(low[u],dfn[it.p1]);continue;} dfs1(it.p1,u);low[u]=min(low[u],low[it.p1]); if(low[it.p1]>dfn[u])mark.insert(m_p(u,it.p1)),mark.insert(m_p(it.p1,u)); } } void dfs2(int u,int b){ bel[u]=b; for(auto it:v[u])if((!bel[it.p1])&&(!mark.count(m_p(u,it.p1))))dfs2(it.p1,b); } int siz[maxn],mxs[maxn],vis[maxn]; ll dis[maxn],res; vector<pair<ll,int> >A,B; vector<int>Node; void dfs4(int u,int fa){ Node.p_b(u); for(auto it:G[u])if((!vis[it.p1])&&it.p1!=fa)dis[it.p1]=dis[u]+it.p2,dfs4(it.p1,u); } void dfs5(int u,int fa){ Node.p_b(u); siz[u]=1,mxs[u]=0; for(auto it:G[u])if((!vis[it.p1])&&it.p1!=fa)dfs5(it.p1,u),siz[u]+=siz[it.p1],mxs[u]=max(mxs[u],siz[it.p1]); } void dfs3(int u){ //cout<<"dfs3 "<<u<<endl; vis[u]=1; dis[u]=0,Node.clear();dfs4(u,0); A.clear(),B.clear(); for(int x:Node)A.p_b(m_p(dis[x],cnt[x])); sort(A.begin(),A.end()); int sz=(int)A.size();up(i,1,sz-1)A[i].p2+=A[i-1].p2; //for(int x:Node)cout<<x<<" "<<dis[x]<<endl;cout<<endl; for(auto it:G[u])if(!vis[it.p1]){ Node.clear();dfs4(it.p1,0); B.clear();for(int x:Node)B.p_b(m_p(dis[x],cnt[x])); sort(B.begin(),B.end()); int szB=(int)B.size();up(i,1,szB-1)B[i].p2+=B[i-1].p2; //cout<<"!!!"<<endl; //for(auto it:B)cout<<it.p1<<" "<<it.p2<<endl; //cout<<endl; //for(auto it:A)cout<<it.p1<<" "<<it.p2<<endl; //cout<<endl<<endl; for(int x:Node){ //cout<<"! "<<x<<" "<<res<<" "<<dis[x]<<endl; auto it=upper_bound(A.begin(),A.end(),m_p(k-dis[x],int(1e9))); if(it!=A.begin())it--,res+=cnt[x]*1ll*((*it).p2); //cout<<"now : "<<res<<endl; auto jt=upper_bound(B.begin(),B.end(),m_p(k-dis[x],int(1e9))); if(jt!=B.begin())jt--,res-=cnt[x]*1ll*((*jt).p2); //cout<<"! "<<x<<" "<<res<<endl; } } auto it=upper_bound(A.begin(),A.end(),m_p(k,int(1e9)));it--; res+=cnt[u]*1ll*((*it).p2-cnt[u]); for(auto it:G[u])if(!vis[it.p1]){ Node.clear();dfs5(it.p1,u); for(int x:Node)mxs[x]=max(mxs[x],(int)Node.size()-siz[x]); int pos=Node[0]; for(int x:Node)if(mxs[x]<mxs[pos])pos=x; dfs3(pos); } } void sub2(){ dfs1(1,0); up(i,1,n)if(!bel[i])++N,dfs2(i,N); up(i,1,n)cnt[bel[i]]++; //up(i,1,n)printf("%d ",bel[i]);printf("\n"); set<pi>E; up(i,1,n)for(auto it:v[i])if(bel[i]!=bel[it.p1]&&(!E.count(m_p(bel[i],bel[it.p1])))){ E.insert(m_p(bel[i],bel[it.p1])),E.insert(m_p(bel[it.p1],bel[i])); G[bel[i]].p_b(m_p(bel[it.p1],it.p2)),G[bel[it.p1]].p_b(m_p(bel[i],it.p2)); } //up(i,1,N)for(auto it:G[i])printf("%d %d %d\n",i,it.p1,it.p2); //up(i,1,N)printf("%d ",cnt[i]);printf("\n"); dfs5(1,0);for(int x:Node)mxs[x]=max(mxs[x],N-siz[x]); int pos=1;for(int x:Node)if(mxs[x]<mxs[pos])pos=x; dfs3(pos);res/=2; up(i,1,N)res+=cnt[i]*1ll*(cnt[i]-1)/2; printf("%lld\n",res); } void slv(){ n=read(),m=read(),k=read(); up(i,1,m){ int x=read(),y=read(),w=read(); v[x].p_b(m_p(y,w)),v[y].p_b(m_p(x,w)); } if(n<=2000){sub1();return;} sub2(); } int main(){ //freopen("graph.in","r",stdin); //freopen("graph.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }