显然是类似k短路，直接不停增广即可
好久没写A*了，裸的A*可能会TLE
加点剪枝就卡过去了………
type node=record
po,next:longint;
cost:double;
end;
point=record
loc:longint;
num:double;
end; var e,ee:array[..] of node;
d:array[..] of double;
q:array[..] of longint;
h:array[..] of point;
p,pp:array[..] of longint;
v:array[..] of boolean;
ans,t,x,y,i,len,n,m:longint;
z,te:double; procedure swap(var a,b:point);
var c:point;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y:longint; z:double);
begin
e[i].po:=y;
e[i].next:=p[x];
e[i].cost:=z;
p[x]:=i;
end; procedure eadd(x,y:longint; z:double);
begin
ee[i].po:=y;
ee[i].next:=pp[x];
ee[i].cost:=z;
pp[x]:=i;
end; procedure spfa;
var f,r,i,x,y:longint;
begin
for i:= to n- do
d[i]:=1e40;
d[n]:=;
f:=;
r:=;
q[]:=n;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=pp[x];
while i<> do
begin
y:=ee[i].po;
if d[y]>d[x]+ee[i].cost then
begin
d[y]:=d[x]+ee[i].cost;
if not v[y] then
begin
v[y]:=true;
inc(r);
q[r]:=y;
end;
end;
i:=ee[i].next;
end;
inc(f);
end;
end; procedure sift(i:longint);
var j:longint;
begin
j:=i shl ;
while j<=t do
begin
if (j<t) and (h[j].num>h[j+].num) then inc(j);
if h[i].num>h[j].num then
begin
swap(h[i],h[j]);
i:=j;
j:=j shl ;
end
else break;
end;
end; procedure up(i:longint);
var j:longint;
begin
j:=i shr ;
while j> do
begin
if h[i].num<h[j].num then
begin
swap(h[i],h[j]);
i:=j;
j:=j shr ;
end
else break;
end;
end; procedure astar;
var i,x,y:longint;
dis:double; begin
h[].loc:=;
h[].num:=d[];
t:=;
while t> do
begin
x:=h[].loc;
dis:=h[].num-d[x];
swap(h[],h[t]);
dec(t);
sift();
if x=n then
begin
if te<dis then break
else begin
inc(ans);
te:=te-dis;
end;
// writeln(te,' ',dis);
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if dis+e[i].cost+d[y]<=te then
begin
inc(t);
h[t].loc:=y;
h[t].num:=dis+e[i].cost+d[y];
up(t);
end;
i:=e[i].next;
end;
end;
end; begin
readln(n,m,te);
for i:= to m do
begin
readln(x,y,z);
add(x,y,z);
eadd(y,x,z);
end;
spfa;
astar;
writeln(ans);
end.