import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import heapq pop,push=heapq.heappop,heapq.heappush class mincf: inf=2*10**18 class E: def __init__(self,to,cap,cost,nx): self.to=to self.cap=cap self.cost=cost self.nx=nx self.rev=None def __init__(self, n): self.n=n self.head=[None]*n self.h=[0]*n self.d=[0]*n self.pre=[None]*n def ae(self,a,b,cap,cost): head=self.head head[a]=self.E(b,cap,cost,head[a]) head[b]=self.E(a,0,-cost,head[b]) head[a].rev=head[b] head[b].rev=head[a] def go(self,s,t,f): inf=self.inf n=self.n head=self.head h=self.h d=self.d pre=self.pre pq=[(0,s)] d[0]=0 d[1:]=[inf]*(n-1) while pq: (a,v)=pop(pq) if d[v]0: w=d[v]+e.cost+h[v]-h[e.to] if w0: a,c=self.go(s,t,f) if a==0: break amount+=a f-=a cost+=a*c return (amount,cost) n, m = map(int, input().split()) s, t, w = 0, n - 1, n G = mincf(n + 2 * m) def add(u, v, c, d): global w G.ae(u, w, 2, c) G.ae(w, v, 1, 0) G.ae(w, v, 1, d - c) w += 1 for i in range(m): u, v, c, d = map(int, input().split()) u -= 1 v -= 1 add(u, v, c, d) add(v, u, c, d) f,res = G.calc(s,t,2) assert f == 2 print(res)