from collections import deque n,m = map(int,input().split()) e = [[] for i in range(n+1)] for i in range(m): u,v,c,d = map(int,input().split()) e[u].append([v,c,d]) e[v].append([u,c,d]) dis = [10**20]*(n+1) dis[1] = 0 par = [-1]*(n+1) q = deque([1]) while q: now = q.popleft() for nex,c,d in e[now]: if dis[nex] > dis[now]+c: dis[nex] = dis[now]+c par[nex] = now q.append(nex) ans = dis[n] now = n while par[now] != -1: p = par[now] for i in range(len(e[now])): if e[now][i][0] == p: e[now][i][1] = -1 break for i in range(len(e[p])): if e[p][i][0] == now: e[p][i][1] = -1 break now = p dis = [10**20]*(n+1) dis[n] = 0 q = deque([n]) while q: now = q.popleft() for nex,c,d in e[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[1] print(ans)