#include<bits/stdc++.h> using namespace std; int t,n,m; const int Maxn=1000001; struct edge{ int v,w,pre; }e[Maxn*2]; int idx,last[Maxn]; void add(int u,int v,int w) { e[++idx]={v,w,last[u]}; last[u]=idx; } int in[505]; int l[505]; void dfs(){ memset(l,0x3f,sizeof(l)); l[1]=0; for(int i=1;i<=n;i++){ int u=0; for(int j=1;j<=n;j++){ if(!in[j]&&l[u]>l[j]) u=j; } in[u]=1; for(int j=last[u];j;j=e[j].pre){ int v=e[j].v; int w=e[j].w; if(!in[v]&&l[v]>w+l[u]){ l[v]=w+l[u]; } } } } int main(){ freopen("dijkstra.in","r",stdin); freopen("dijkstra.out","w",stdout); cin>>t>>n>>m; memset(e,0x3f,sizeof(e)); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } dfs(); int sum=0; for(int i=1;i<=n;i++){ if(l[i]<=t) sum++; } cout<<sum; return 0; }

114514