/**
 *    author:  mamion
 *    created: Sunday 2024-10-27
**/

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include<cpp-dump-main/cpp-dump.hpp>
#define debug(...) cpp_dump(__VA_ARGS__)
CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
#else
#define debug(...)
#endif // LOCAL

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9;
const int N = 1e4 + 10, M = 1e3 + 10;
int numNode, numEdge, moneyLim;
vector<tuple<int, int, int>> adj[N];

pair<int, int> f[N][2];

void dijkstra() {
    memset(f, 0x3f, sizeof f);
    f[1][0] = f[1][1] = {0, -moneyLim};
    priority_queue<tuple<int, int, int, int>> pq;
    pq.push({0, moneyLim, 1, 0}); pq.push({0, moneyLim, 1, 1});
    while (pq.size()) {
        int dist = -get<0>(pq.top()); int money = get<1>(pq.top());
        int u = get<2>(pq.top()); int state = get<3>(pq.top());
        pq.pop();
        if (dist != f[u][state].first || -money != f[u][state].second) continue;
        for (auto p : adj[u]) {
            int v = get<0>(p), c = get<1>(p), d = get<2>(p);
            if (state == 1) c++; else d++;
            // go by bike here
            int moneyBike = money, wBike = 0;
            if (moneyBike < c) {
                moneyBike = min(moneyLim, money + (c - money + 99 - 1) / 99 * 99);
                wBike = (c - money + 99 - 1) / 99;
            }
            moneyBike -= c;
            if (f[v][0] > make_pair(f[u][state].first + wBike + c, -moneyBike)) {
                f[v][0] = {f[u][state].first + wBike + c, -moneyBike};
                pq.push({-f[v][0].first, moneyBike, v, 0});
            }

            // go by bus here
            int moneyBus = money, wBus = 0;
            if (moneyBus < d) {
                moneyBus = min(moneyLim, money + (d - money + 99 - 1) / 99 * 99);
                wBus = (d - money + 99 - 1) / 99;
            }
            moneyBus -= d;
            if (f[v][1] > make_pair(f[u][state].first + wBus + d, -moneyBus)) {
                f[v][1] = {f[u][state].first + wBus + d, -moneyBus};
                pq.push({-f[v][1].first, moneyBus, v, 1});
            }
        }
    }
}

void solve() {
    cin >> numNode >> numEdge;
    for (int i = 0; i < numEdge; i++) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        adj[u].push_back({v, c, d});
        adj[v].push_back({u, c, d});
    }
    cin >> moneyLim;
    dijkstra();
    int ans = inf;
    ans = min(ans, f[numNode][0].first);
    ans = min(ans, f[numNode][1].first);
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
#else
    #define file "name"
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }
#endif // LOCAL

    int T; T = 1; if (0) cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
}