iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。 能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！ 注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

第一行三个数 N、M、E 表示iPig知道的元素个数（元素从 1 到 N 编号）、iPig已经学会的魔法个数和iPig的总能量。 后跟 M 行每行三个数 si、ti、ei 表示 iPig 知道一种魔法，消耗 ei 的能量将元素 si 变换到元素 ti 。

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

using namespace __gnu_pbds;

inline int rd() {

    register int x=0;

    register char s=getchar();

    while(s<'0'||s>'9') s=getchar();

    while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=getchar();

    return x;

}

typedef double f2;

#define N 5050

#define M 200050

int head[N],to[M],nxt[M],cnt,n,m,xx[M],yy[M],vis[N],tot[N],ans;

f2 val[M],zz[M],dis[N],lft;

__attribute__((optimize("-O2")))struct node {

    f2 v;

    int x;

    node() {}

    node(f2 v_,int x_) :

        v(v_),x(x_) {}

    inline bool operator < (const node &u) const {

        return v+dis[x]>u.v+dis[u.x];

    }

};

__gnu_pbds::priority_queue<pair<f2,int> >q1;

__gnu_pbds::priority_queue<node>q2;

__attribute__((optimize("-O2")))inline void add(int u,int v,f2 w) {

    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;

}

__attribute__((optimize("-O2")))void dij() {

    memset(dis,0x7f,sizeof(dis));

    dis[n]=0; q1.push(make_pair(0,n));

    while(!q1.empty()) {

        int x=q1.top().second,i; q1.pop();

        if(vis[x]) continue;

        vis[x]=1;

        for(i=head[x];i;i=nxt[i]) {

            if(dis[to[i]]>dis[x]+val[i]) {

                dis[to[i]]=dis[x]+val[i];

                q1.push(make_pair(-dis[to[i]],to[i]));

            }

        }

    }

}

__attribute__((optimize("-O2")))void _A_stAr_SapPh1r3_() {

    f2 inf=lft/dis[1];

    q2.push(node(0,1));

    while(!q2.empty()) {

        node t=q2.top(); q2.pop();

        int x=t.x;

        f2 v=t.v;

        // printf("%f\n",lft);

        int i;

        if(x==n) {

            if(lft>=v) {

                lft-=v; ans++;

            }else {

                printf("%d\n",ans); exit(0);

            }

        }

        for(i=head[x];i;i=nxt[i]) {

            q2.push(node(v+val[i],to[i]));

        }

    }

}

__attribute__((optimize("-O2")))int main() {

    n=rd(); m=rd(); scanf("%lf",&lft);

    int i;

    for(i=1;i<=m;i++) {

        xx[i]=rd(); yy[i]=rd(); scanf("%lf",&zz[i]);

        add(yy[i],xx[i],zz[i]);

    }

    dij();

    //lft/=dis[1];

    memset(head,0,sizeof(head)); cnt=0;

    for(i=1;i<=m;i++) {

        add(xx[i],yy[i],zz[i]);

    }

    _A_stAr_SapPh1r3_();

    printf("%d\n",ans);

}