from copy import deepcopy
from collections import deque
n,m = map(int,input().split())
e = [[] for i in range(n)]
for i in range(m):
    u,v,c,d = map(int,input().split())
    u -= 1
    v -= 1
    e[u].append([v,c,d])
    e[v].append([u,c,d])
def search(a,b,g):

    dis = [10**20]*n
    dis[a] = 0
    par = [-1]*n
    q = deque([a])
    while q:
        now = q.popleft()
        for nex,c,d in g[now]:
            if dis[nex] > dis[now]+c:
                dis[nex] = dis[now]+c
                par[nex] = now
                q.append(nex)
    ans = dis[b]
    now = b
    while par[now] != -1:
        p = par[now]
        for i in range(len(g[now])):
            if g[now][i][0] == p:
                g[now][i][1] = -1
                break
        now = p
    dis = [10**20]*n
    dis[b] = 0
    q = deque([b])
    while q:
        now = q.popleft()
        for nex,c,d in g[now]:
            if c == -1:
                if dis[nex] > dis[now]+d:
                    dis[nex] = dis[now]+d
                    q.append(nex)
            else:
                if dis[nex] > dis[now]+c:
                    dis[nex] = dis[now]+c
                    q.append(nex)
    ans += dis[a]
    return ans
print(min(search(0,n-1,deepcopy(e)),search(n-1,0,deepcopy(e))))