import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
U = 10 ** 5
inf = 10**18

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
cost = dict()
for _ in range(m):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    edge[a].append(b)
    edge[b].append(a)
    cost[a * U + b] = (c, d)

dist = [inf] * n
prev = [-1] * n
dist[0] = 0
que = [(0, 0)]
while que:
    ds, s = heapq.heappop(que)
    if dist[s] < ds:
        continue
    for t in edge[s]:
        a, b = min(s, t), max(s, t)
        dt = cost[a * U + b][0]
        if dist[t] > ds + dt:
            dist[t] = ds + dt
            prev[t] = s
            heapq.heappush(que, (ds + dt, t))
ans = dist[n - 1]
s = n - 1
while prev[s] != -1:
    t = prev[s]
    a, b = min(s, t), max(s, t)
    c, d = cost[a * U + b]
    cost[a * U + b] = (d, -1)
    s = t


dist = [inf] * n
dist[n - 1] = 0
que = [(0, n - 1)]
while que:
    ds, s = heapq.heappop(que)
    if dist[s] < ds:
        continue
    for t in edge[s]:
        a, b = min(s, t), max(s, t)
        dt = cost[a * U + b][0]
        if dist[t] > ds + dt:
            dist[t] = ds + dt
            heapq.heappush(que, (ds + dt, t))

ans += dist[0]
print(ans)