from collections import defaultdict


class Graph:
    def __init__(self):
        self.ways = defaultdict(list)
        self.node = set()

    def add_node(self, num):
        self.node.add(num)

    def add_edge(self, num, start, finish):
        self.ways[(start, finish)].append(num)


def dekstra(n, s, graph, count):
    visited = set()
    length = list()
    for i in range(n):
        if i != s:
            length.append(100500)
        else:
            length.append(0)
    for i in range(n):
        min_num = 100500
        min_index = -1
        for i in range(n):
            if i not in visited and length[i] < min_num:
                min_index = i
                min_num = length[i]
        for i in range(n):
            if (min_index, i) in graph.ways:
                for q in graph.ways[(min_index, i)]:
                    if int(q) + length[min_index] < length[i] \
                            and count <= cups[(min_index, i)]:
                        length[i] = int(q) + length[min_index]
        visited.add(min_index)
    return length


def real(count):
    if dekstra(n, 0, graph, count)[n - 1] <= 1440:
        return True
    return False


def binary_search():
    left = 0
    right = 10000000
    while left < right:
        centre = (left + right) // 2
        if real(centre):
            left = centre + 1
            if not real(left):
                return centre
        else:
            right = centre
    return right


maximum = 0
cups = dict()
n, m = map(int, input().split())
if n == 1:
    print(10000000)
    exit(0)
graph = Graph()
for i in range(n):
    graph.add_node(i)
for i in range(m):
    fro, to, time, count = map(int, input().split())
    cups[(fro - 1, to - 1)] = (count - 3000000) // 100
    cups[(to - 1, fro - 1)] = (count - 3000000) // 100
    if (fro - 1 == 0 or to - 1 == 0) and maximum < (count - 3000000) // 100:
        maximum = (count - 3000000) // 100
    graph.add_edge(time, fro - 1, to - 1)
    graph.add_edge(time, to - 1, fro - 1)
print(binary_search())