#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=205,M=5e4+5;
void upd(int &mx,int &mx2,int t){
	if (t<=mx) mx2=mx,mx=t;
	else if (t<mx2) mx2=t;
}
int n,m,s,tmp[N],dis[N],rdis[N],din[N],rdin[N],tdis[N],rtdis[N],e[N][N],e2[N][N],to[N][N],ans;
vector<int>pa[N],rpa[N];
struct node{
	int u,v,w,d;
}l[M];
void dijkstra(int d[],vector<int>p[],int op=1){
	int cnt=0,u=s;
	for (int i=1;i<=n;i++){
		d[i]=(i!=s)*1e18;
		tmp[i]=0;
	}
	if (op) p[s].push_back(s);
//	for (int i=1;i<=n;i++){
//		for (int j=1;j<=n;j++)
//			cout<<e[i][j]<<' ';
//		cout<<'\n';
//	}
	while (cnt<n){
//		cout<<u<<' ';
		if (u==-1) break;
		tmp[u]=1,cnt++;
		for (int v=1;v<=n;v++){
			if (v==u||e[u][v]==1e18) continue;
			int w=e[u][v];
			if (!tmp[v]&&d[u]+w<d[v]){
				d[v]=d[u]+w;
				if (op) p[v]=p[u],p[v].push_back(v);
			}
		}
		int mn=1e18;u=-1;
		for (int i=1;i<=n;i++){
			if (tmp[i]) continue;
			if (d[i]<mn) mn=d[i],u=i;
		}
//		for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<'\n';
	}
//	cout<<'\n';
}
signed main(){
	n=read(),m=read(),s=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			e[i][j]=e2[i][j]=(i!=j)*1e18;
	for (int i=1;i<=m;i++){
		int u=read(),v=read(),w=read(),d=read();
		upd(e[u][v],e2[u][v],w),l[i]={u,v,w,d};
	}
	dijkstra(dis,pa);
	for (int t=2;t<=n;t++) if (pa[t].size()) for (int i=0;i<pa[t].size()-1;i++) to[pa[t][i]][pa[t][i+1]]=1;
	ans=dis[n];
	s=n,dijkstra(rdis,rpa);
	for (int t=1;t<n;t++) if (rpa[t].size()) for (int i=0;i<rpa[t].size()-1;i++) to[rpa[t][i]][rpa[t][i+1]]=1;
	ans+=rdis[1];
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			swap(e[i][j],e[j][i]);
	s=n,dijkstra(din,pa,0);
	s=1,dijkstra(rdin,pa,0);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			swap(e[i][j],e[j][i]);
//	cout<<ans<<'\n';
	for (int i=1;i<=m;i++){
		int res=l[i].d;
		if (!to[l[i].u][l[i].v]){
			res+=min(dis[n],dis[l[i].v]+din[l[i].u]+l[i].w);
			res+=min(rdis[1],rdis[l[i].v]+rdin[l[i].u]+l[i].w);
		}
		else{
//			cout<<"Jb\n";
			int xx=e[l[i].u][l[i].v],xy=e[l[i].v][l[i].u];
			e[l[i].v][l[i].u]=min(e[l[i].v][l[i].u],l[i].w);
			if (e[l[i].u][l[i].v]==l[i].w) e[l[i].u][l[i].v]=e2[l[i].u][l[i].v];
			s=1,dijkstra(tdis,pa,0);
			s=n,dijkstra(rtdis,pa,0);
//			for (int i=1;i<=n;i++) cout<<tdis[i]<<' ';cout<<'\n';
//			for (int i=1;i<=n;i++) cout<<rtdis[i]<<' ';cout<<'\n';
			res+=tdis[n]+rtdis[1];
//			cout<<tdis[n]<<' '<<rtdis[1]<<'\n';
			e[l[i].v][l[i].u]=xy,e[l[i].u][l[i].v]=xx;
		}
//		cout<<l[i].u<<' '<<l[i].v<<' '<<res<<'\n';
		ans=min(ans,res);
	}
	if (ans>=1e18) cout<<"-1";
	else cout<<ans;
	return 0;
}

record