#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
const int N=1e6+7;
const ll INF=1e18;
ll dis[N];ll n,m,h;
struct node{ll k,b,to;};
vector<node> G[N];
ll check(ll x) {
    for(ll i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(pii(1,0));
    while(!q.empty()) {
        ll u=q.top().fi;ll d=q.top().sc;
        q.pop();
        if(dis[u]<d) continue;
        for(auto t:G[u]) {
            ll v=t.to,k=t.k,b=t.b;
            if(dis[v]>dis[u]+1ll*k*x+b) {
                dis[v]=dis[u]+1ll*k*x+b;
                q.push(pii(v,dis[v]));
            }
        }
    }return dis[n];
}
int main() {
    cin>>n>>m>>h;
    for(ll i=1;i<=m;i++) {
        ll u,v,k,b;scanf("%lld %lld %lld %lld",&u,&v,&k,&b);
        G[u].pb(node{k,b,v});
    }
    ll l=0,r=h;
    while(l+10<r) {
        ll mid=l+r>>1;
        ll smid=r+mid>>1;
        if(check(mid)>check(smid)) r=smid;
        else l=mid;
    }
    ll ans=-INF;
    for(ll i=l;i<=r;i++) {
        ans=max(ans,check(i));
    }printf("%lld\n",ans);
    return 0;
}