#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<bitset>
#include<cstring>
using namespace std;

constexpr int NMAX = 1e3 + 10;
constexpr long long INF = 1e16;

long long flow[NMAX][NMAX],cap[NMAX][NMAX],cost[NMAX][NMAX],t[NMAX];
vector<int> vecini[NMAX];
vector<long long> dist;
bitset<NMAX> inq;

bool bf(int s,int e)
{
    fill(dist.begin(),dist.end(),INF); dist[s] = 0; memset(t,0,sizeof(t));
    queue<int> q; q.push(s); inq.reset(); inq[s] = 1;
    while(!q.empty())
        {
            int v = q.front(); q.pop(); inq[v] = 0;
            for(auto it : vecini[v])
                {
                    if((cap[v][it] - flow[v][it]) > 0)
                        {
                            if(dist[it] > dist[v] + cost[v][it])
                                {
                                    dist[it] = dist[v] + cost[v][it]; t[it] = v;
                                    if(!inq[it])
                                        {
                                            inq[it] = 1;
                                            q.push(it);
                                        }
                                }
                        }
                }
        }

    return (dist[e] != INF);
}

int main()
{
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);

    int n,m,s,e,a,b,c,d; cin >> n >> m; s = 1,e = n;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b >> c >> d;
            vecini[a].emplace_back(b);
            vecini[b].emplace_back(a);
            cap[a][b] = c; cost[a][b] = d;
            cost[b][a] = -d;
        }

    long long ans = 0,flux = 0; dist.resize(n + 1);
    while(bf(s,e))
        {
            long long delta = INF;
            for(int v = e; v != s; v = t[v]) delta = min(delta,(long long)(cap[t[v]][v] - flow[t[v]][v]));
            for(int v = e; v != s; v = t[v]) flow[t[v]][v] += delta,flow[v][t[v]] -= delta;

            ans += 1LL * delta * dist[e];
        }


    cout << ans;
}