#include<bits/stdc++.h> #define ll long long #define lson pos<<1 #define rson pos<<1|1 using namespace std; const int maxn=3e5+10; const ll mod=1e9+7; const ll inf=1e10; ll n,m,k,t,cnt=0; ll dfn[maxn],belong[maxn],tsiz[maxn],son[maxn][20],fa[maxn][20],dep[maxn],sum[maxn],low[maxn]; char c[maxn][30]; int stk[maxn],tp=0,tot=0; bool instk[maxn]; vector< pair<int,ll> >q[maxn],q1[maxn]; void dfs(int pos,int from){ dep[pos]=dep[from]+1; int siz=q[pos].size(); for(int i=0;i<siz;i++){ int v=q[pos][i].first; if(v==from) continue; // cout<<v<<" "<<pos<<" "<<i<<endl; fa[v][0]=pos; sum[v]=sum[pos]+q[pos][i].second; for(int j=0;j<18;j++){ fa[v][j+1]=fa[fa[v][j]][j]; } dfs(v,pos); } } void dfs1(int pos,int from){ //cout<<pos<<" "<<from<<endl; tot++; dfn[pos]=low[pos]=tot; instk[pos]=1,stk[++tp]=pos; int siz=q[pos].size(); for(int i=0;i<siz;i++){ int v=q[pos][i].first; if(v==from) continue; if(!dfn[v]){ dfs1(v,pos); low[pos]=min(low[pos],low[v]); } else if(instk[v]){ low[pos]=min(low[pos],dfn[v]); } } if(low[pos]==dfn[pos]){ ++cnt; while(tp){ int x=stk[tp--]; tsiz[cnt]++; instk[x]=0; belong[x]=cnt; if(x==pos) break; } } } void dfs2(int pos,int from){ // cout<<pos<<" "<<from<<endl; dep[pos]=dep[from]+1; int siz=q1[pos].size(); for(int i=0;i<siz;i++){ int v=q1[pos][i].first; if(v==from) continue; fa[v][0]=pos; //cout<<v<<" "<<pos<<" "<<sum[v]<<" "<<sum[pos]<<" "<<q1[pos][i].second<<endl; sum[v]=sum[pos]+q1[pos][i].second; for(int j=0;j<18;j++){ fa[v][j+1]=fa[fa[v][j]][j]; } dfs2(v,pos); } } int _lca(int x,int y){ // cout<<x<<" "<<y<<endl; if(dep[x]<dep[y]) swap(x,y); for(int i=18;i>=0;i--){ // cout<<dep[y]<<" "<<dep[0]<<endl; if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; } if(x==y) return x; //cout<<x<<" "<<y<<endl; for(int i=18;i>=0;i--){ if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } struct node{ int u,v; ll w; }edge[maxn]; int main(){ //freopen("graph.in","r",stdin); //freopen("graph.out","w",stdout); memset(dep,0,sizeof(dep)); memset(sum,0,sizeof(sum)); memset(fa,0,sizeof(fa)); scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=m;i++){ int u,v; ll w; scanf("%d%d%lld",&u,&v,&w); edge[i]=(node){u,v,w}; q[u].push_back(make_pair(v,w)); q[v].push_back(make_pair(u,w)); } if(m==n-1){ dfs(1,0); // cout << _lca(4, 5) << endl; ll cnt=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(sum[i]+sum[j]-2ll*sum[_lca(i,j)]<=k) cnt++; } } printf("%lld\n",cnt); fclose(stdin); fclose(stdout); return 0; } dfs1(1,0); for(int i=1;i<=m;i++){ int l=belong[edge[i].u],r=belong[edge[i].v]; if(l==r) continue; //cout<<l<<" "<<r<<" "<<edge[i].w<<endl; q1[l].push_back(make_pair(r,edge[i].w)); q1[r].push_back(make_pair(l,edge[i].w)); } //cout<<cnt<<endl; dfs2(1,0); ll cnt1=0; for(int i=1;i<=cnt;i++){ cnt1+=(tsiz[i]*(tsiz[i]-1))/2; for(int j=i+1;j<=cnt;j++){ //cout<<_lca(i,j)<<" "<<sum[i]<<" "<<sum[j]<<" "<<2ll*sum[_lca(i,j)]<<endl; if(sum[i]+sum[j]-2ll*sum[_lca(i,j)]<=k) cnt1+=tsiz[i]*tsiz[j]; } } printf("%lld",cnt1); fclose(stdin); fclose(stdout); return 0; }