#include<iostream>
#include<queue>
#include<cstring>
#define maxn 5001
using namespace std;
struct Edge{ int v,nxt; double w; }edge[200001];
struct Node{
	int v; double len; 
	bool operator <(const Node &r) const {
		return r.len<len;
	}
};
int head[maxn],n,m,cnt,vis[maxn],ans;
void add(int u,int v,double w){ edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].nxt=head[u],head[u]=cnt; }
double e,dis[maxn];
void Dijkstra(){
	memset(dis,0x3f,sizeof dis);
	dis[n]=0;
	priority_queue <Node> q;
	q.push({n,0});
	while (!q.empty()){
		Node t=q.top(); q.pop();
		int u=t.v;
		if (vis[u]) continue;
		vis[u]=1;
		for (int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].v;
			if (dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				q.push({v,dis[v]});
			}
		}
	}
}
void A_Star(){
	priority_queue <pair<double,pair<double,int> >,vector< pair<double,pair<double,int> > >,greater<pair<double,pair<double,int> > > > q;
	// 估价 + 真实值 ；真实值 ；编号 
	q.push(make_pair(dis[1],make_pair(0,1))); 
//	int tot[maxn]={0};
	while (!q.empty()){
		auto t=q.top(); q.pop();
		int u=t.second.second; double distance=t.second.first;
		if (u==n){
			if (distance<=e){
				ans++,e-=distance; // e 是总能量数！ 
			}
			else return;
		}
		for (int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].v;
			q.push(make_pair(dis[v]+distance+edge[i].w,make_pair(distance+edge[i].w,v)));
		}
	}
}
int main(){
	cin>>n>>m>>e;
	for (int i=1;i<=m;i++){
		int u,v; double w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	Dijkstra(); 
	A_Star();
	cout<<ans;
	return 0;
}

rt，知道 A_Star 过不了，期望是 UAC 100 pts，实际上 MLE 40pts 求助各位，谢谢