打了一发可持久化左偏树的k短路，#4、#11都MLE，下载孔爷的数据（#11）自测发现左偏树上节点个数非常巨大，约有1.2e7个点，不知是否因为我写错了。 改为随机堆后通过。 代码如下，如有不对请指出

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define Side(x) for(int i=p[x];i;i=nt[i])
using namespace std;
typedef pair<double,int> pdi;
const int N=100020,M=500020;
const double eps=1e-10;
int n,m,tot,e[M],nt[M],p[N];
double se,w[M];
struct Edge
{
    int u,v;
    double w;
    int id;
}edge[M];
inline void _add(int x,int y,double z){e[++tot]=y,nt[tot]=p[x],w[tot]=z,p[x]=tot;}
double dis[N];
inline bool dCmp(double a,double b){return a<b?(b-a<eps):(a-b<eps);}
int fa[N];
bool onT[M],vis[N];
priority_queue<pdi,vector<pdi>,greater<pdi> >q;
void dijkstra(int s)
{
    for(int i=1;i<=n;i++)dis[i]=INFINITY;
    dis[s]=0,q.push((pdi){0,s});
    while(!q.empty())
    {
        int fr=q.top().second;q.pop();
        if(vis[fr])continue;
        vis[fr]=true;
        Side(fr)
        {
            if(dis[e[i]]>dis[fr]+w[i])
            {
                dis[e[i]]=dis[fr]+w[i];
                q.push((pdi){dis[e[i]],e[i]});
            }
        }
    }
}
void dfs(int x)
{
    vis[x]=true;
    Side(x)
    {
        if(!vis[e[i]]&&dCmp(dis[e[i]],dis[x]+w[i]))
            dfs(e[i]),onT[i]=true;
    }
}
struct hpnode
{
    double key;
    int dis,v;
    hpnode *ch[2];
    hpnode(double _key,int _v):key(_key),dis(1),v(_v){ch[0]=ch[1]=nullptr;}
};
typedef hpnode* hptr;
typedef pair<double,hptr> pdh;
hptr h[N],recycle[N*200];
int tp;
priority_queue<pdh,vector<pdh>,greater<pdh> >q1;
hptr merge(hptr x,hptr y)
{
    if(!x||!y)return x?x:y;
//	cerr<<x<<' '<<y<<endl;
    if(x->key>y->key)swap(x,y);
    hptr cur=new hpnode(*x);
    recycle[++tp]=cur;
    cur->ch[1]=merge(cur->ch[1],y);
//	cerr<<"cur ch:"<<cur->ch[0]<<' '<<cur->ch[1]<<endl;
    if(cur->ch[0]&&cur->ch[0]->dis<cur->ch[1]->dis)swap(cur->ch[0],cur->ch[1]);
    cur->dis=cur->ch[1]->dis+1;
    return cur;
}
void buildT()
{
    memset(vis,0,sizeof(vis));
    dfs(n);
    memset(p,0,sizeof(p)),tot=0;
    for(int i=1;i<=m;i++)
        if(!onT[edge[i].id]&&dis[edge[i].u]<INFINITY)_add(edge[i].u,edge[i].v,edge[i].w);
        else fa[edge[i].u]=edge[i].v;
    for(int u=1;u<=n;u++)
    {
//		cerr<<u<<':';
        Side(u)
        {
//			cerr<<e[i]<<' ';
            h[u]=merge(h[u],recycle[++tp]=(new hpnode(dis[e[i]]+w[i]-dis[u],e[i])));
        }
//		cerr<<endl;
    }
    cerr<<tp<<endl;
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)q.push((pdi){dis[i],i});
    while(!q.empty())
    {
        int tp=q.top().second;q.pop();
//		cerr<<tp<<' '<<fa[tp]<<' '<<h[tp]<<' '<<h[fa[tp]]<<endl;
        h[tp]=merge(h[tp],h[fa[tp]]);
    }
}
void solve()
{
    int ans=0;
    if(dis[1]<=se)se-=dis[1],ans++;
    if(h[1])q1.push((pdh){h[1]->key,h[1]});
    while(!q1.empty())
    {
        double enow=q1.top().first;
        hptr cur=q1.top().second;
//		cerr<<enow<<','<<se<<endl;
        if(se>=enow+dis[1])se-=enow+dis[1],ans++;
        else break;
        q1.pop();
        if(cur->ch[0])q1.push((pdh){enow+cur->ch[0]->key-cur->key,cur->ch[0]});
        if(cur->ch[1])q1.push((pdh){enow+cur->ch[1]->key-cur->key,cur->ch[1]});
        if(h[cur->v])q1.push((pdh){enow+h[cur->v]->key,h[cur->v]});
    }
    printf("%d",ans);
}
int main()
{
	freopen("11.in","r",stdin);
    scanf("%d%d%lf",&n,&m,&se);
    int ui,vi;double wi;
    for(int i=1;i<=m;i++)
        scanf("%d%d%lf",&ui,&vi,&wi),_add(vi,ui,wi),edge[i]={ui,vi,wi,tot};
    dijkstra(n);
    buildT();
    solve();
}