struct node{    int v,cap,next;}; node edges[N];int head[N],e; void add(int u,int v,int cap){    edges[e].v=v;    edges[e].cap=cap;    edges[e].next=head[u];    head[u]=e++;} void Add(int u,int v,int cap){    add(u,v,cap);    add(v,u,0);} int pre[N],cur[N],num[N],h[N]; int Maxflow(int s,int t,int n){    int i;    for(i=0;i<=n;i++) cur[i]=head[i],num[i]=h[i]=0;    int u=s,Min,k,v;    int ans=0;    while(h[u]<n)    {        if(u==t)        {            Min=INF;            for(i=s;i!=t;i=edges[cur[i]].v)            {                k=cur[i];                if(edges[k].cap<Min) Min=edges[k].cap,v=i;            }            ans+=Min; u=v;            for(i=s;i!=t;i=edges[cur[i]].v)            {                k=cur[i];                edges[k].cap-=Min;                edges[k^1].cap+=Min;            }        }        for(i=cur[u];i!=-1;i=edges[i].next)        {            if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) break;        }        if(i!=-1)        {            cur[u]=i;            pre[edges[i].v]=u;            u=edges[i].v;        }        else        {            if(--num[h[u]]==0) break;            k=n;            cur[u]=head[u];            for(i=head[u];i!=-1;i=edges[i].next)            {                if(edges[i].cap>0&&h[edges[i].v]<k)                {                    k=h[edges[i].v];                }            }            num[k+1]++;            h[u]=k+1;            if(u!=s) u=pre[u];        }    }    return ans;}struct Node{    int u,v,w,c,next;};Node edge[300000];int head1[505],e1;void add1(int u,int v,int w,int c){    edge[e1].u=u;    edge[e1].v=v;    edge[e1].w=w;    edge[e1].c=c;    edge[e1].next=head1[u];    head1[u]=e1++;}int n,m,dis1[505],dis2[505];int inq[505];void BFS(int dis[],int s){    int i;    FOR1(i,n) dis[i]=INF,inq[i]=0;    queue<int> Q;     Q.push(s);    dis[s]=0;    int u,v;    while(!Q.empty())    {        u=Q.front();        Q.pop();                inq[u]=0;                for(i=head1[u];i!=-1;i=edge[i].next)        {            v=edge[i].v;            if(dis[v]>dis[u]+edge[i].w)            {                dis[v]=dis[u]+edge[i].w;                if(!inq[v]) inq[v]=1,Q.push(v);            }        }    }}void build(){    clr(head,-1);    int i,u,v,c;    FOR0(i,e1)    {        u=edge[i].u;        v=edge[i].v;        c=edge[i].c;        if(dis1[u]+edge[i].w+dis2[v]==dis1[n])        {            if(u!=n&&v!=1) Add(u,v,c);        }    }}int main(){    RD(n,m); clr(head1,-1);    int i,u,v,w,c;    FOR1(i,m)    {        RD(u,v); RD(w,c);        add1(u,v,w,c);        add1(v,u,w,c);    }    BFS(dis1,1);  BFS(dis2,n);    build(); PR(dis1[n]);    PR(Maxflow(1,n,n));}