def dijkstra(g, start, finish, glasses):
    used = {start}
    dist = [10 ** 10] * (cv + 1)
    dist[start] = 0
    while len(used) != cv and finish not in used:
        minE = 10 ** 10
        thisV = -1
        for u in used:
            for v in g[u]:
                if v[0] not in used:
                    if dist[u] + v[1] <= minE and v[2] >= glasses:
                            minE = dist[u] + v[1]
                            thisV = v[0]
        if thisV == -1:
            break
        used.add(thisV)
        dist[thisV] = minE
    if dist[finish] > 1440:
        return False
    else:
        return True


def binSearch(g, start, finish):
    l = 0
    r = 10000000
    m = 0
    while l != r:
        m = (l+r+1) // 2
        if dijkstra(g, start, finish, m):
            l = m
        else:
            r = m - 1
    return r


cv, ce = map(int, input().split())
start, finish = 1, cv
maxInt = 10 ** 10
g = [[] for i in range(cv+1)]
for i in range(ce):
    tempU, tempF, time, weight = map(int, input().split())
    weight = (weight - 3 * 10 ** 6) // 100
    if weight > 0:
        g[tempU].append([tempF, time, weight])
print(binSearch(g, start, finish))