#yukicoder276D

'''
3ヶ月ぶりの挑戦。

めちゃくちゃフローに見える。計算量が大丈夫な保証まったくないけどやってみるか。
→最小費用流の計算量はO(FE logV) らしい。F=2なら大丈夫だろ。
'''
f=lambda:map(int,input().split())
N,M=f()

#最小費用流 Vを入力してください
V=N #入力してください

G=[[] for i in range(V)]; INF=10**64         # V: 頂点数
def add_edge(u, v, cap, cost):               # 最小費用流を見据えて、辺にコストの情報を保持
    G[u].append((v,cap, cost,len(G[v])  ))   # 順辺: (移動先,容量,費用,逆辺番号)のtuple型
    G[v].append((u,  0,-cost,len(G[u])-1))   # 逆辺: コストを負値にする
                                             #
def bellman_ford(s):                         #
    dist=[INF]*V; dist[s]=0                  # 全辺をdist=INFで初期化する
    Pv,Pe=[0]*V,[0]*V                        # 始点からの具体的な最短距離を求めるため用意
    while True:                              #   Pv[v]: 距離更新時に通った頂点
        update=False                         #   Pe[v]: Pv[v]の何番目の辺を用いたか
        for v in range(V):                   # 
            if dist[v]==INF: continue        # 頂点vに考慮が及んでいない時はskipする
            for i in range(len(G[v])):       # G[v]: 遷移先, 容量, 費用, (逆辺の番号)
                nxt,cap,cost,_=G[v][i]       # G[v][i]: 頂点vのi番目の辺
                if cap>0 and dist[nxt]>dist[v]+cost:
                    dist[nxt]=dist[v]+cost   # 容量0の辺は無視する点に注意
                    update=True              # 距離更新ができた時は次回もループを回す
                    Pv[nxt],Pe[nxt]=v,i      # 更に、距離更新用の頂点・辺情報を記録する
        if not update: break                 #
    return dist,Pv,Pe                        # 距離。最短路用の頂点・辺情報を返す
                                             #
def Calc_mincost(st,fin,fL):                 # fL: 流したい水総量
    result=0                                 #
    while fL>0:                              #
        dist,Pv,Pe=bellman_ford(st)          # ベルマンフォード法で現時点の最短路を決定
        if dist[fin]==INF: return INF        # 条件を満たせない場合はINFを返す
        flow=fL; v=fin                       #
        while v!=st:                         # ①最短路に流せる水量上限を測定
            flow=min(flow,G[Pv[v]][Pe[v]][1])# 終点から最短路を逆走しながら水量上限を測定
            v=Pv[v]                          # vをひとつ前の頂点に戻す 始点に戻るまで反復
        result+=flow*dist[fin]               # 始点に戻った時点で、最終的なフローと距離から
        fL-=flow; v=fin                      # コストを計上する。さらにフローの計上処理へ
        while v!=st:                         # ②使用した最大水量で通過した辺を更新
            u,cap,cost,rev=G[Pv[v]][Pe[v]]   # 順辺更新: revの情報は保持しておく
            cap-=flow                        # list型よりtuple型のほうが高速なのでバラす
            G[Pv[v]][Pe[v]]=(u,cap,cost,rev) # 容量だけ更新してtupleで戻す
            u,cap,cost,rev2=G[v][rev]        # 逆辺更新: revの情報をそのまま使う
            cap+=flow                        # rev2は順辺番号にあたる
            G[v][rev]      =(u,cap,cost,rev2)#
            v=Pv[v]                          # 順辺逆辺を更新したらひとつ前に戻る
    return result                            # 総費用をreturn お疲れ様でした

for _ in range(M):
    u,v,c,d=f()
    add_edge(u-1,v-1,1,c); add_edge(u-1,v-1,1,d)
    add_edge(v-1,u-1,1,c); add_edge(v-1,u-1,1,d)
print(Calc_mincost(0,N-1,2))