Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 510

#define MAXM 124800

#define INF 0x3f3f3f3f

struct dinic

{

	int s,t;

	struct edge

	{

		int to,nxt,f;

	}e[MAXM << 1];

	int edgenum;

	int lin[MAXN];

	dinic(){edgenum = 0;memset(lin,-1,sizeof(lin));}

	void add(int a,int b,int f)

	{

		e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

		e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

		return;

	}

	int ch[MAXN];

	bool BFS()

	{

		queue<int> q;q.push(s);

		memset(ch,-1,sizeof(ch));ch[s] = 0;

		while(!q.empty())

		{

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

			for(int i = lin[k];i != -1;i = e[i].nxt)

			{

				if(ch[e[i].to] == -1 && e[i].f)

				{

					ch[e[i].to] = ch[k] + 1;

					q.push(e[i].to);

				}

			}

		}

		return ch[t] != -1;

	}

	int flow(int k,int f)

	{

		if(k == t)return f;

		int r = 0;

		for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

		{

			if(ch[e[i].to] == ch[k] + 1 && e[i].f)

			{

				int l = flow(e[i].to,min(e[i].f,f - r));

				e[i].f -= l;r += l;e[i ^ 1].f += l;

			}

		}

		if(r == 0)ch[k] = -1;

		return r;

	}

	int calc()

	{

		int ans = 0,r;

		while(BFS())while(r = flow(s,INF))ans += r;

		return ans;

	}

}f; 

struct dijkstra

{

	struct edge

	{

		int to,nxt,v,f;

	}e[MAXM << 1];

	int edgenum;

	int lin[MAXN];

	dijkstra()

	{

		memset(lin,0,sizeof(lin));

		edgenum = 0;

	}

	void add(int a,int b,int v,int f)

	{

		++edgenum;e[edgenum].to = b;e[edgenum].v = v;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;

		++edgenum;e[edgenum].to = a;e[edgenum].v = v;e[edgenum].f = f;e[edgenum].nxt = lin[b];lin[b] = edgenum;

		return;

	}

	int dis[2][MAXN];

	bool v[MAXN];

	#define d dis[type]

	void calc(int type,int s)

	{

		priority_queue< pair<int,int> > q;q.push(make_pair(0,s));

		memset(d,0x3f,sizeof(d));d[s] = 0;

		memset(v,false,sizeof(v));

		while(!q.empty())

		{

			int k = q.top().second;q.pop();

			if(v[k])continue;

			v[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(d[e[i].to] > d[k] + e[i].v)

				{

					d[e[i].to] = d[k] + e[i].v;

					q.push(make_pair(-d[e[i].to],e[i].to));

				}

			}

		}

		return;

	}

	void work()

	{

		calc(0,1);calc(1,n);

		for(int k = 1;k <= n;++k)

		{

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(dis[0][k] + e[i].v + dis[1][e[i].to] == dis[0][n])

				{

					f.add(k,e[i].to,e[i].f);

				}

			}

		}

		return;

	}

}p; 

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,x,y;

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

	{

		scanf("%d%d%d%d",&a,&b,&x,&y);

		p.add(a,b,x,y);

	}

	p.work();f.s = 1;f.t = n;

	cout << p.dis[0][n] << endl;

	cout << f.calc() << endl;

	return 0;

}