import sys
input = sys.stdin.readline
enum = enumerate
inf = 1001001001002002002
MOD = 998244353 #10**9 + 7

import collections
import random
from bisect import bisect_right as bs_r
from itertools import permutations
import heapq

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in range(rep))

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def dist(x1,y1,x2,y2):
	return abs(x1-x2)+abs(y1-y2)

vD = [chr(ord("a")+i) for i in range(26)]

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)
	
def csum(v):
	vr = [0,]
	s = 0
	for a in v:
		s = (s+a)	
		vr.append(s)
	return vr

def dijkstra(start, n, c_list):
    _vC = [inf,]*(n+1)
    _vC[start] = 0
    _vR = [0,]*(n+1) #set({})
    _vQ = [(0,start),]
    heapq.heapify(_vQ)
    while _vQ:
        _ci,_i = heapq.heappop(_vQ)
        if _vC[_i] < _ci:
            continue
        for _cj,_j,_m in c_list[_i]:
            if _vC[_j] > _vC[_i] + _cj:
                _vC[_j] = _vC[_i] + _cj
                #_vM |= {_m,}
                _vR[_j] = _i
                heapq.heappush(_vQ, (_vC[_j],_j))
    return _vC, _vR

def main():
	N,M = linput()
	mT = [linput(int,tuple) for _ in range(M)]
	
	res = 0
	
	# 1st graph
	mG = [[] for _ in range(N+1)]
	for m, (u,v,c,d) in enum(mT):
		mG[u].append( (c,v,m) )
		mG[v].append( (c,u,m) )
	
	# dijkstra 1
	vC, vR = dijkstra(1, N, mG)
	print(vC, vR)###
	res += vC[N]	
	
	# find a path
	vM = set({})
	vQ = [N,]
	while vQ:
		v = vQ.pop()
		u = vR[v]
		for c,gv,m in mG[u]:
			if gv==v:
				vQ.append(u)
				vM |= {m,}
				break
	
	# 2nd graph
	mG = [[] for _ in range(N+1)]
	for m, (u,v,c,d) in enum(mT):
		cost = d if m in vM else c
		mG[u].append( (cost,v,m) )
		mG[v].append( (cost,u,m) )
	
	# dijkstra 2
	vC, vR = dijkstra(N, N, mG)	
	#print(vC)###
	res += vC[1]
	
	print(res)


	
if __name__ == "__main__":
	main()