#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6;
double dis[N + 5],e;
int n,m,vis[N + 5],parts[N + 5],cnt,root[N + 5],ans = 1,s[N + 5];
bool cmp(int x,int y){
	return dis[x] < dis[y];
}
struct Node{
	int id;
	double dis;
	bool operator < (const Node &x) const {
		return dis > x.dis;
	}
};
priority_queue<Node> q; // 大根堆
struct node{
	int x;
	double ans;
	bool operator < (const node &x) const {
		return ans > x.ans;
	}
}; 
priority_queue<node> qq; // 大根堆变小跟堆
struct Edge{
	int to,nxt;
	double dis;
};
struct Add{
	int tot = 0,head[N + 5];
	Edge edge[N + 5]; 
	void add (int u,int v,int w){
		edge[++ tot] = (Edge){v,head[u],w};
		head[u] = tot;
	}
}Head,Tail;
void dij(){
	q.push((Node){n,0});
	memset (dis,127,sizeof dis);
	dis[n] = 0;
	while (q.size()){
		Node u = q.top();
		q.pop();
		vis[u.id] = 1;
		for (int i = Tail.head[u.id];i;i = Tail.edge[i].nxt){
			Node v = (Node){Tail.edge[i].to,u.dis + Tail.edge[i].dis};
			if (vis[u.id]){
				if (dis[v.id] > v.dis){
					dis[v.id] = v.dis;
					parts[v.id] = i; // 记录最短路树上指向点v.id的边的编号 
					q.push(v);
				}
			}
		}
	}
}
// 可持久化左偏树 
struct heap{
	int lft,rgt,dis,part;
	double k;
}tree[N << 1];
int treeadd(int f,double value){
	int k = ++ cnt;
	tree[k].lft = tree[k].rgt = tree[k].dis = 0;
	tree[k].part = f,tree[k].k = value;
	return k;
}
int merge(int x,int y){ // 可持久化左偏树所有操作基于merge
	if (!x || !y) return x + y;
	if (tree[x].k - tree[y].k > 0) swap(x,y);
	int k = ++ cnt;
	tree[k] = tree[x];
	tree[k].rgt = merge (tree[k].rgt,y);
	if (tree[tree[k].lft].dis < tree[tree[k].rgt].dis) swap (tree[k].lft,tree[k].rgt);
	tree[k].dis = tree[tree[k].rgt].dis + 1;
	return k; 
}
signed main(){
	cin >> n >> m >> e;
	for (int i = 1;i <= m;i ++){
		int x,y;
		double z;
		cin >> x >> y >> z;
		if (x == n){
			i --;
			m --; 
			continue; // 去掉以n为起点的边 
		}
		Head.add (x,y,z),Tail.add (y,x,z);
	}
	dij();
	for (int i = 1;i <= n;i ++) s[i] = i;
	sort (s + 1,s + 1 + n,cmp);  // 建立可持久化左偏树来维护与每个点及其最短路树上的祖先相连的非树边 
	tree[0].dis = -1;
	for (int i = 1;i <= n;i ++){
		int u = s[i];
		for (int j = Head.head[u];j;j = Head.edge[j].nxt){
			if (parts[u] != j) root[u] = merge (root[u],treeadd (Head.edge[j].to,Head.edge[j].dis + dis[Head.edge[j].to] - dis[u]));
		}
		root[u] = merge(root[u],root[Head.edge[parts[u]].to]);
	}
	e -= dis[1];
	if (e < 0) cout << 0 << endl; // 没效果
	if (root[1]) qq.push((node){root[1],tree[root[1]].k});
	while (qq.size()){
		node u = qq.top();
		qq.pop();
		e -= u.ans + dis[1];
		if (e < 0) break;
		if (tree[u.x].lft) qq.push((node){tree[u.x].lft,u.ans - tree[u.x].k + tree[tree[u.x].lft].k});
		if (tree[u.x].rgt) qq.push((node){tree[u.x].rgt,u.ans - tree[u.x].k + tree[tree[u.x].rgt].k});
		if (root[tree[u.x].part]) qq.push((node){root[tree[u.x].part],u.ans + tree[root[tree[u.x].part]].k});
		ans ++;
		// 替换某为起点的这条边为一条刚好大于等于它的非树边。尾部接上一条起点为以某为起点的这条边的终点在某中祖先(包括自己)连出去的所有非树边的最小边。
	} 
	cout << ans - 1 << endl;
	return 0;
}