#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct line{
	int to;
	int dis;
}b;
vector<line>a[40010];
queue<int>q;
int d[40010];
int vis[40010];
int n,m,minn=0x7ffffff;
int find(int he)
{
	for(int i=0;i<a[he].size();i++)
	{
		if(a[he][i].to==1) return i;
	}
}
void work()
{
	for(int i=0;i<a[1].size ();i++)
	{
		int he=a[1][i].to;
		int k=find(he);
		int dist=a[he][k].dis;
		a[he][k].dis=99999999;
		memset(d,127/3,sizeof(d));
		memset(vis,0,sizeof(vis));
		d[he]=0;
		vis[he]=1;
		q.push(he);
		while(q.size()>0)
		{
			int u=q.front();
			q.pop();
			vis[u]=0;
			for(int i=0;i<a[u].size();i++)
			{
				if(d[a[u][i].to]>d[u]+a[u][i].dis)
				{
					d[a[u][i].to]=d[u]+a[u][i].dis;
					if(!vis[a[u][i].to])
					{
						q.push(a[u][i].to);
						vis[a[u][i].to]=1;
					}
				}
			}
		}
		a[he][k].dis=dist;
		printf("%d %d\n",d[1],a[1][i].dis);
		d[1]=d[1]+a[1][i].dis;
		if(d[1]<minn) minn=d[1];
	}
}
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,c1,c2;
		scanf("%d%d%d%d",&u,&v,&c1,&c2);
		b.to=v;
		b.dis=c1;
		a[u].push_back(b);
		b.to=u;
		b.dis=c2;
		a[v].push_back(b);
	}
	work();
	if(minn!=0x7ffffff)
	printf("%d",minn);
	else printf("%d",-1);
	return 0;
}