1967

#include <iostream>
//#include <chrono>
//#include <fstream>
//#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int INF = 1e18;

vector<vector<pi>> mat;
int n;

bool foo(int count_cup) {
    vector<ll> d(n, INF);
    d[0] = 0;
    vector<bool> used(n);
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++)
            if ((v == -1 || d[j] < d[v]) && !used[j])
                v = j;
        if (d[v] == INF)
            break;
        used[v] = 1;
        for (int j = 0; j < n; j++)
            if ((ll)mat[v][j].first + d[v] < d[j] && mat[v][j].second >= count_cup)
                d[j] = (ll)mat[v][j].first + d[v];
    }
    return d[n - 1] <= 1440;
}

int main() {
    /*ifstream cin("in.txt");
    ofstream cout("out.txt");
    auto start_time = chrono::high_resolution_clock::now();*/

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m;
    cin >> n >> m;
    if (m == 0 || n == 1) {
        cout << int(1e7) << "\n";
        return 0;
    }
    mat.assign(n, vector<pi>(n));
    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        d = (d - 3e6) / 100;
        mat[--a][--b] = mp(c, d);
        mat[b][a] = mp(c, d);
    }

    int l = 0, r = 10000100;
    while (l < r) {
        int mid = (l + r) / 2;
        if (foo(mid))
            l = mid + 1;
        else
            r = mid;
    }
    cout << max(0, l - 1) << "\n";

    /*auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end_time - start_time;
    cout << duration.count() << "\n";
    cin.close();
    cout.close();*/
    return 0;
}