A*裸题，，，
#include<cstdio>
#include<queue>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
#define ri register int
#define rd register double
#define I inline __attribute((always_inline))
#define pdi pair<double,int>
#define fir first
#define sec second
#define add(u,v,w){e[++cnt]=(edge){v,h[u],w};h[u]=cnt;}
using namespace std;
const int N=5001,M=2e5+1;
typedef __gnu_pbds::priority_queue<pdi,greater<pdi> > heap;
I int read(){
ri x=0,f=1,c=getchar();
for(;c< '0'||c> '9';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=x*10+c-48;
return x*f;
}
int n,m,u,v,s,t;double en,w;
heap q;
namespace Ii {
struct edge{int to,nxt;double w;}e[M];
int h[N],cnt;bool vis[N];
I void ins(ri u,ri v,rd w)
{e[++cnt]=(edge){v,h[u],w};h[u]=cnt;}
I void dij(ri s,ri t,rd *d){
for(ri i=1;i<=n;++i) d[i]=1e15;
d[s]=0;q.push(make_pair(0,s));
while(!q.empty()){
ri u=q.top().sec;q.pop();
if(vis[u]) continue;vis[u]=1;
for(ri i=h[u],v;i;i=e[i].nxt)
if(d[v=e[i].to] > d[u] +e[i].w)
d[v]=d[u]+e[i].w,q.push(make_pair(d[v],v));
}
}
}
struct edge{int to,nxt;double w;}e[M];
int h[N],cnt;
double d_t[N];int vis[N];
I void A_star(ri s,ri t){
Ii::dij(t,s,d_t);
q.push(make_pair(d_t[s],s));
while(!q.empty()){
ri u=q.top().sec;rd d=q.top().fir;q.pop();
if(u == t ) if((en-=d) < 0) return;
vis[u]++;

for(ri i=h[u];i;i=e[i].nxt)
q.push(make_pair(d-d_t[u]+d_t[e[i].to]+e[i].w,e[i].to));
}
}
int main() {
n=read();m=read();scanf("%lf",&en);s=1;t=n;
for(ri i=1;i<=m;++i) {u=read();v=read();scanf("%lf",&w);Ii::ins(v,u,w);add(u,v,w);}
A_star(s,t);
printf("%d\n",vis[t]);
return 0;
}