#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <climits>
#include <queue>


class Graph {
    int size;
    std::vector<std::vector<int>> data;
    std::vector<std::vector<int>> merge;
    std::vector<std::vector<int>> roads;
    std::vector<bool> isused;
    std::queue<int> que;
public:
    Graph(int n) {
        size = n;
        data.resize(n);
        merge.resize(n);
        roads.resize(n);
        for (int i = 0; i < n; ++i) {
            data[i].resize(n, 2000);
            roads[i].resize(n, 0);
        }
        isused.resize(n, false);
    }

    void insert(int a, int b, int c, int d) {
        if (a != b) {
            data[a - 1][b - 1] = c;
            data[b - 1][a - 1] = c;
            roads[a - 1][b - 1] = d;
            roads[b - 1][a - 1] = d;
            merge[a - 1].push_back(b - 1);
            merge[b - 1].push_back(a - 1);
        }
    }

    bool shortest_way(int a, int b, int w) {
        std::vector<int> result(size, 2000);
        result[a - 1] = 0;
        std::queue<int> empty;
        std::swap(que, empty);
        que.push(a - 1);
        while (que.size() != 0) {
            int vertex = que.front();
            que.pop();
            for (auto i : merge[vertex]) {
                if (result[i] > result[vertex] + data[vertex][i] && roads[vertex][i] >= w) {
                    result[i] = result[vertex] + data[vertex][i];
                    que.push(i);
                }
            }
        }
        if (result[b - 1] > 1440) {
            return false;
        } else {
            return true;
        }
    }

    int bin_search(int left, int right, int a, int b) {
        while (left < right - 1) {
            int curr = (left + right) / 2;
            if (shortest_way(a, b, curr)) {
                left = curr;
            } else {
                right = curr;
            }
        }
        return left;
    }

    int transport(int a, int b) {
        int left = 0;
        int right = 10000001;
        return bin_search(left, right, a, b);
    }

};

int main() {
    int n, m;
    std::cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        d = (d - 3000000) / 100;
        g.insert(a, b, c, d);
    }
    std::cout << g.transport(1, n);
}