#include<bits/stdc++.h> using namespace std; int t,n,m; int ma[505][505]; int in[505]; int dis[505]; void dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1]=0; for(int i=1; i<=n; i++) { int u=0; for(int j=1; j<=n; j++) if(!in[j]&&(u==0 || dis[j]<dis[u]))u=j; in[u]=1; for(int j=1; j<=n; j++) if(!in[j]&&ma[u][j]+dis[u]<dis[j]) dis[j]=ma[u][j]+dis[u]; } } int main(){ freopen("dijkstra.in","r",stdin); freopen("dijkstra.out","w",stdout); cin>>t>>n>>m; memset(ma,0x3f,sizeof(ma)); int x,y,z; for(int i=1; i<=m; i++) { cin>>x>>y>>z; if(z<ma[x][y]) { ma[x][y]=z; ma[y][z]=z; } } dijkstra(); int ans=0; for(int i=1; i<=n; i++) if(dis[i]<=t)ans++; cout<<ans; return 0; }