#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define maxv 105

#define maxe 100500

#define inf 1000000000

using namespace std;

int n,m,a[maxv],b[maxv],c[maxv],d[maxv],s,t,fin[maxv],fout[maxv],g[maxv],dis[maxv],nume=,ans=,pree[maxv],prev[maxv];

bool vis[maxv];

queue <int> q;

struct edge

{

    int v,f,c,nxt;

}e[maxe];

void addedge(int u,int v,int f,int c)

{

    e[++nume].v=v;e[nume].nxt=g[u];

    e[nume].f=f;e[nume].c=c;g[u]=nume;

    e[++nume].v=u;e[nume].nxt=g[v];

    e[nume].f=;e[nume].c=-c;g[v]=nume;

}

bool spfa()

{

    for (int i=s;i<=t;i++) {vis[i]=false;dis[i]=inf;}

    dis[s]=;q.push(s);

    while (!q.empty())

    {

        int head=q.front();q.pop();

        for (int i=g[head];i;i=e[i].nxt)

        {

            int v=e[i].v;

            if ((e[i].f) && (dis[v]>dis[head]+e[i].c))

            {

                dis[v]=dis[head]+e[i].c;

                pree[v]=i;prev[v]=head;

                if (!vis[v]) {vis[v]=true;q.push(v);}

            }

        }

        vis[head]=false;

    }

    if (dis[t]==inf) return false;

    return true;

}

int dinic()

{

    int u=t,dt=inf;

    while (u!=s)

    {

        dt=min(dt,e[pree[u]].f);

        u=prev[u];

    }

    u=t;

    while (u!=s)

    {

        e[pree[u]].f-=dt;

        e[pree[u]^].f+=dt;

        u=prev[u];

    }

    return dis[t]*dt;

}

int main()

{

    scanf("%d%d",&n,&m);s=;t=n+;

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

    {

        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

        fout[a[i]]+=d[i];fin[b[i]]+=d[i];

    }

    for (int i=;i<=n;i++)

    {

        if (fin[i]>fout[i]) addedge(s,i,fin[i]-fout[i],);

        else addedge(i,t,fout[i]-fin[i],);

    }

    addedge(n,,inf,);

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

    {

        if (d[i]>c[i])

        {

            addedge(a[i],b[i],inf,);

            addedge(b[i],a[i],d[i]-c[i],);

            addedge(b[i],a[i],c[i],);

            ans+=d[i]-c[i];

        }

        else

        {

            addedge(a[i],b[i],c[i]-d[i],);

            addedge(a[i],b[i],inf,);

            addedge(b[i],a[i],d[i],);

        }

    }

    while (spfa()) ans+=dinic();

    printf("%d\n",ans);

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000050

#define mod 1000000007

using namespace std;

long long n,k,prime[maxn/],tot=,mn[maxn],ans=,tab[maxn],kr=,num[maxn];

bool vis[maxn];

void get_table()

{

    mn[]=;

    for (long long i=;i<=maxn-;i++)

    {

        if (!vis[i]) {vis[i]=true;prime[++tot]=i;mn[i]=i;}

        for (long long j=;j<=tot && i*prime[j]<=maxn-;j++)

        {

            vis[i*prime[j]]=true;mn[i*prime[j]]=prime[j];

            if (!i%prime[j]) break;

        }

    }

}

long long ask(long long x,long long cnt)

{

    if (x==-) return ;

    long long lim=,ret=,ans=;tab[]=;

    while (tab[ret]<=cnt) tab[++ret]=tab[ret-]*x+1LL;

    ret--;

    for (long long i=ret;i>=;i--)

    {

        ans=ans*x+cnt/tab[i];

        cnt%=tab[i];

    }

    return ans*x;

}

int main()

{

    scanf("%lld%lld",&n,&k);

    get_table();

    for (long long i=;i<=n;i++)

    {

        long long x=i,ret1=-,cnt=,rr;

        while (x!=)

        {

            if (mn[x]!=ret1) {ans=max(ans,ask(ret1,num[ret1]*k));ret1=mn[x];}

            num[mn[x]]++;

            rr=mn[x];x/=mn[x];

        }

        ans=max(ans,ask(ret1,num[rr]*k));cnt=;

        kr=(kr+ans)%mod;

    }

    printf("%lld\n",kr);

    return ;

}