参考博客https://blog.csdn.net/u013534123/article/details/97142191

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+50;

int S,T,From[maxn],Laxt[maxn],Next[maxn],To[maxn];

ll Cap[maxn],cnt;

int vd[maxn],dis[maxn];

void add(int u,int v,ll c){

    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;Cap[cnt]=c;From[cnt]=u;

    Next[++cnt]=Laxt[v];Laxt[v]=cnt;To[cnt]=u;Cap[cnt]=0;From[cnt]=v;

}

ll sap(int u,ll flow,int limit){

    if(u==T||flow==0)return flow;

    ll tmp,delta=0;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i];

        if(dis[u]==dis[v]+1&&Cap[i]){

            tmp=sap(v,min(flow-delta,Cap[i]),limit);

            Cap[i]-=tmp;Cap[i^1]+=tmp;delta+=tmp;

            if(dis[S]>=limit||delta==flow)return delta;

        }

    }

    vd[dis[u]]--;if(!vd[dis[u]])dis[S]=limit;

    vd[++dis[u]]++;

    return delta;

}

void init(int limit){

    cnt=1;

    for(int i=0;i<=limit;i++)Laxt[i]=dis[i]=vd[i]=0;

}

int main(){

    std::ios::sync_with_stdio(false);

    int n,m;

    while(cin>>n>>m){

        init(n+2);

        S=0,T=n+1;

        ll ans=0;

        for(int i=1;i<=m;i++){

            ll u,v,a,b,c;

            cin>>u>>v>>a>>b>>c;

            ans+=(a+b+c)*2;

            add(u,T,a/4+4*c/3);

            add(v,T,a/4+4*c/3);

            add(S,u,5*a/4+c/3);

            add(S,v,5*a/4+c/3);

            add(u,v,c/3+a/2);

            add(v,u,c/3+a/2);

        }

        ll pp=0;

        while(dis[S]<n+2){

            pp+=sap(S,1e9,n+2);

        }

        cout<<(ans-pp)/2<<endl;

    }

    return 0;

}