def solve() -> None:
    n, m = invr()

    graph: list[list[tuple[int, int, int]]] = [[] for _ in range(n)]
    goated_tunnels: set[tuple[int, int]] = set()
    sum_c: int = 0
    for i in range(m):
        a, b, c, r = invr()
        a -= 1
        b -= 1
        sum_c += c
        graph[a].append((b, c, r))
        graph[b].append((a, c, r))
        if r > c:
            goated_tunnels.add((a, b))
            goated_tunnels.add((b, a))

    low: int = 0
    high: int = sum_c

    def check(mid: int) -> bool:
        stack: list[tuple[int, int]] = [(-mid, 0)]  # (-coins, node)
        visited: set[int] = set()  # (node: coins)
        while stack:
            coins: int
            node: int
            coins, node = heapq.heappop(stack)
            coins = -coins
            if node in visited:
                continue
            visited.add(node)
            for neighbour, cost, reward in graph[node]:
                if coins >= cost:
                    if (node, neighbour) in goated_tunnels:
                        return True
                    if neighbour == n - 1:
                        return True
                    if neighbour not in visited:
                        heapq.heappush(stack, (-(coins - cost + reward), neighbour))
        return False

    while low < high:
        mid: int = (low + high) // 2
        if check(mid):
            high = mid
        else:
            low = mid + 1

    print(low)