code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Edge{
    int to,next;
    double w;
}e[1000005],e2[1000005];
int head[100005],tot;
int n,m,s,t;
double k;
double d[100005];
bool vis[100005];
void add_edge(int u,int v,double w)
{
    e[++tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
}
void dijkstra(int s)
{
    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>>q;
    q.push({0,s});
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(d[v]>d[u]+e[i].w)
            {
                d[v]=d[u]+e[i].w;
                q.push({d[v],v});
            }
        }
    }
}
struct node{
    double len;int x;
    friend bool operator<(const node &x,const node &y)
    {
        return (x.len+d[x.x])>(y.len+d[y.x]);
    }
};
int cnt,Vis[100005];
double sum;
int A_star(int s)
{
    priority_queue<node>q;
    q.push((node){0,s});
    while(!q.empty())
    {
        node u=q.top();q.pop();
        Vis[u.x]++;
        if(u.x==t&&u.len)
        {
            cnt++;sum+=u.len;
            if(sum>k)return cnt-1;
        }
        for(int i=head[u.x];i;i=e[i].next)
            if(Vis[e[i].to]<k)q.push((node){e[i].w+u.len,e[i].to});
    }
    return -1;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v;double w;
        cin>>u>>v>>w;
        if(u<v)swap(u,v);
        add_edge(v,u,w);
        e2[i]=(Edge){u,v,w};
    }
    s=n,t=1;
    dijkstra(t);
    memset(d,0,sizeof(d));
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=1;i<=m;i++)
        add_edge(e2[i].to,e2[i].next,e2[i].w);
    cout<<A_star(s);
    return 0;
}