import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
N, M = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c, d = map(int, input().split())
    X[a-1].append([b-1, c, d, -1])
    X[b-1].append([a-1, c, d, X[a-1][-1]])
    X[a-1][-1][-1] = X[b-1][-1]

def dijkstra(n, E, i0=0, tp=0):
    s, t = 0, n - 1
    kk = 18
    mm = (1 << kk) - 1
    h = [i0]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        x = hpop(h)
        d, i = x >> kk, x & mm
        if done[i]: continue
        done[i] = 1
        for j, w, _, _ in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, (nd << kk) + j)
                    D[j] = nd
    if tp: return D[-1]
    i = t
    PT = [t]
    while i != s:
        for k, (j, w, _, _) in enumerate(E[i]):
            if D[i] == D[j] + w:
                E[i][k][1] = E[i][k][2]
                E[i][k][3][1] = E[i][k][3][2]
                i = j
                PT.append(i)
                break
    return D[-1]

print(dijkstra(N, X) + dijkstra(N, X, 0, 1))