#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define maxm 200010
#define maxn 30005
#define inf (1<<30)
using namespace std;
int tot,len[maxm],end[maxm],last[maxm],next[maxm],N,M,dis[maxn];
bool mark[maxn];
void add(int x,int y,int w)
{
	len[++tot]=w;
	end[tot]=y;
	next[tot]=last[x];
	last[x]=tot;
}
void spfa(int s)
{
	int i,t;
	queue<int>Q;
	for(i=1;i<=N;i++)
	{
		dis[i]=inf;
		mark[i]=0;
	}
	Q.push(s);dis[s]=0;mark[s]=1;
	while(!Q.empty())
	{
		t=Q.front();mark[t]=0;Q.pop();
		for(i=last[t];i;i=next[i])
		{
			if(dis[end[i]]>dis[t]+len[i])
			{
				dis[end[i]]=dis[t]+len[i];
				if(!mark[end[i]])
				{
					mark[end[i]]=1;
					Q.push(end[i]);
				}
			}
		}
	}
}
int main()
{
	freopen("zaw.in","r",stdin);
	freopen("zaw.out","w",stdout);
	int i,j,x,y,w,ww,len1n=inf,lenn1=inf,a,b;
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d%d%d%d",&x,&y,&w,&ww);
//		if((x==1)&&(y==N))len1n=w,lenn1=ww;
//		else if((x==N)&&(y==1))len1n=ww,lenn1=w;
		
		
			add(x,y,w);
			add(y,x,ww);
		
	}
	bool flag=1;
	int ans=inf;
	for(a=last[1];a;a=next[a])
	{
		int t=len[a],tt;
//		printf("==%d==\n",end[a]);
		len[a]=inf;
		for(b=last[end[a]];b;b=next[b])
			if(end[b]==1)
			{
				tt=len[b];
				break;
			}
		len[b]=inf;
		spfa(1);
	//	for(a=1;a<=N;a++)printf("-%d- ",dis[a]);
//		putchar(10);
//		printf("-%d %d-%d\n",end[a],tt,t);
		ans=min(dis[end[a]]+tt,ans);
		len[a]=t;len[b]=tt;
	}
		
//	printf("-%d-\n",dis[N]);
//	dis[N]+=lenn1;
//	ans=min(ans,dis[N]);
//	flag=1;
	//spfa(N);
//	dis[1]+=lenn1;
//	ans=min(ans,dis[1]);
	if(ans>=inf)puts("-1");
	else printf("%d\n",ans);
	return 0;
}