visited = set()


def dijkstra(N, s, c, nodes):
    weightCup = 100 * c
    time = [100000] * (N + 1)
    time[s] = 0
    for i in range(1, N + 1):
        minTime = 10000000
        nodeMin = -1
        for j in range(1, N + 1):
            if j not in visited and time[j] < minTime:
                nodeMin = j
                minTime = time[j]
        for el in nodes[nodeMin]:
            if el[2] >= weightCup and time[nodeMin] + el[1] < time[el[0]]:
                time[el[0]] = time[nodeMin] + el[1]
        visited.add(nodeMin)
    if time[N] > 1440:
        return True
    else:
        return False


def binarySearch():
    l = 0
    r = 10000001
    while l != r:
        mid = (l + r) // 2
        res = dijkstra(n, s, mid, nodes)
        if res == 1:
            l = mid + 1
        else:
            r = mid
    print(l)


nodes = list()
n, m = map(int, input().split())
for i in range(n + 1):
    nodes.append([])
if n == 1:
    print(10000000)
else:
    for i in range(m):
        start, finish, time, weight = map(int, input().split())
        nodes[start].append([finish, time, weight - 3000000])
        nodes[finish].append([start, time, weight - 3000000])
    s = 1
    binarySearch()