#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<double,int> PII;
const int N=5010,M=2e5+10;
int n,m;
int h[N],e[M],ne[M],rh[N],re[M],rne[M],idx,ridx;
double w[M],rw[M];
void add(int a,int b,double c)
  {
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx]=c;
    re[++ridx]=a;
    rne[ridx]=rh[b];
    rh[a]=ridx;
    rw[ridx]=c;
  }
double f[N];
bool v[N];
void spfa()
  {
      queue<int> q;
      memset(f,0x3f,sizeof(f));
      v[n]=1;
      q.push(n);
      f[n]=0;
      while(!q.empty())
        {
            int x=q.front();
            q.pop();
            v[x]=0;
            for(int i=rh[x];i;i=rne[i])
              if(f[re[i]]>f[x]+rw[i])
                {
                    f[re[i]]=f[x]+rw[i];
                    if(!v[re[i]]) q.push(re[i]);
                    v[re[i]]=1;
                }
        }
  }
int num[N],ans;
double maxw,dist[N];
void Astar(int k)
  {
      priority_queue<PII,vector<PII>,greater<PII> >heap;
      heap.push({f[1],1});
      while(!heap.empty())
        {
            int x=heap.top().second;
            dist[x]=heap.top().first-f[x];
            heap.pop();
            if(dist[x]+f[x]>maxw) return;
            num[x]++;
            if(x==n)
              {
                  ans++;
                  maxw-=dist[n];
                  continue;
              }
            if(num[x]>k) continue;
            for(int i=h[x];i;i=ne[i])
            if(num[e[i]]<k)
            heap.push({dist[x]+w[i]+f[e[i]],e[i]});
        }
  }
signed main() {
    cin>>n>>m>>maxw;
    for(int i=1;i<=m;i++)
      {
          int x,y;
          double z;
          cin>>x>>y>>z;
          add(x,y,z);
      }
    spfa();
    Astar(maxw/f[1]);
    cout<<ans<<endl;
}

只有37分，前两个点WA，其余MLE