#include <cstdio>

#include <cstring>

#include <string>

#include <queue>

#include <cmath>

#include <algorithm>

#define LL long long

using namespace std;

//点的总数为 N，点的编号 1~N

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

struct edge

{

    int to,cap,flow,cost,next;

    edge(){}

    edge(int to,int cap,int flow,int cost,int next):to(to),cap(cap),flow(flow),cost(cost),next(next){}

}e[MAXM];

int head[MAXN],tot;

int pre[MAXN],dis[MAXN];

bool vis[MAXN];

int N,M;

void init(int n)

{

    N=n;

    tot=;

    memset(head,-,sizeof(head));

}

void addedge(int u, int v, int cap, int flow, int cost)

{

    e[tot]=edge(v,cap,flow,cost,head[u]);

    head[u]=tot++;

    e[tot]=edge(u,,,-cost,head[v]);

    head[v]=tot++;

}

bool spfa(int s,int t)

{

    queue<int>q;

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

    {

        dis[i]=INF;

        vis[i]=false;

        pre[i]=-;

    }

    dis[s]=;

    vis[s]=true;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=false;

        for(int i=head[u];~i;i=e[i].next)

        {

            int v=e[i].to;

            if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].cost)

            {

                dis[v]=dis[u]+e[i].cost;

                pre[v]=i;

                if(!vis[v])

                {

                    vis[v]=true;

                    q.push(v);

                }

            }

        }

    }

    if(pre[t]==-) return false;

    else return true;

}

//返回的是最大流， cost存的是最小费用

int minCostMaxflow(int s,int t,int &cost)

{

    int flow=;

    cost=;

    while(spfa(s,t))

    {

        int Min=INF;

        for(int i=pre[t];i!=-;i=pre[e[i^].to])

        {

            if(Min>e[i].cap-e[i].flow)

                Min=e[i].cap-e[i].flow;

        }

        for(int i=pre[t];i!=-;i=pre[e[i^].to])

        {

            e[i].flow+=Min;

            e[i^].flow-=Min;

            cost+=e[i].cost*Min;

        }

        flow+=Min;

    }

    return flow;

}

int main()

{

    int n,m;

    int cas=;

    while(scanf("%d%d",&n,&m)>)

    {

        init(n+);

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

        {

            int u,v,w1,w2;

            scanf("%d%d%d%d",&u,&v,&w1,&w2);

            addedge(u,v,,,w1);

            addedge(u,v,,,w1+w2);

        }

        addedge(,,,,);

        addedge(n,n+,,,);

        int ans=;

        minCostMaxflow(,n+,ans);

        printf("Case %d: %d\n",cas++,ans);

    }

    return ;

}