#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=1,ans=0,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=0;e[nume].c=-c;g[v]=nume;
}
bool spfa()
{
    for (int i=s;i<=t;i++) {vis[i]=false;dis[i]=inf;}
    dis[s]=0;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]^1].f+=dt;
        u=prev[u];
    }
    return dis[t]*dt;
}
int main()
{
    scanf("%d%d",&n,&m);s=0;t=n+1;
    for (int i=1;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=1;i<=n;i++)
    {
        if (fin[i]>fout[i]) addedge(s,i,fin[i]-fout[i],0);
        else addedge(i,t,fout[i]-fin[i],0);
    }
    addedge(n,1,inf,0);
    for (int i=1;i<=m;i++)
    {
        if (d[i]>c[i])
        {
            addedge(a[i],b[i],inf,2);
            addedge(b[i],a[i],d[i]-c[i],0);
            addedge(b[i],a[i],c[i],1);
            ans+=d[i]-c[i];
        }
        else
        {
            addedge(a[i],b[i],c[i]-d[i],1);
            addedge(a[i],b[i],inf,2);
            addedge(b[i],a[i],d[i],1);
        }
    }
    while (spfa()) ans+=dinic();
    printf("%d\n",ans);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000050
#define mod 1000000007
using namespace std;
long long n,k,prime[maxn/5],tot=0,mn[maxn],ans=0,tab[maxn],kr=0,num[maxn];
bool vis[maxn];
void get_table()
{
    mn[1]=1;
    for (long long i=2;i<=maxn-50;i++)
    {
        if (!vis[i]) {vis[i]=true;prime[++tot]=i;mn[i]=i;}
        for (long long j=1;j<=tot && i*prime[j]<=maxn-50;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==-1) return 0;
    long long lim=1,ret=1,ans=0;tab[1]=1;
    while (tab[ret]<=cnt) tab[++ret]=tab[ret-1]*x+1LL;
    ret--;
    for (long long i=ret;i>=1;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=2;i<=n;i++)
    {
        long long x=i,ret1=-1,cnt=0,rr;
        while (x!=1)
        {
            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=1;
        kr=(kr+ans)%mod;
    }
    printf("%lld\n",kr);
    return 0;
}