/**
 *    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];

int f[N][M][2];

void dijkstra() {
    memset(f, 0x3f, sizeof f);
    f[1][moneyLim][0] = f[1][moneyLim][1] = 0;
    priority_queue<tuple<int, int, int, int>> pq;
    pq.push({0, 1, moneyLim, 0}); pq.push({0, 1, moneyLim, 1});
    while (pq.size()) {
        int dist = -get<0>(pq.top()); int u = get<1>(pq.top());
        int money = get<2>(pq.top()); int state = get<3>(pq.top());
        pq.pop();
        if (dist != f[u][money][state]) 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][moneyBike][0] > f[u][money][state] + wBike + c) {
                f[v][moneyBike][0] = f[u][money][state] + wBike + c;
                pq.push({-f[v][moneyBike][0], v, moneyBike, 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][moneyBus][1] > f[u][money][state] + wBus + d) {
                f[v][moneyBus][1] = f[u][money][state] + wBus + d;
                pq.push({-f[v][moneyBus][1], v, moneyBus, 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;
    for (int i = 0; i <= moneyLim; i++) {
        ans = min(ans, f[numNode][i][0]);
        ans = min(ans, f[numNode][i][1]);
    }
    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();
    }
}