#include <bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define P 1007
using namespace std;
const int N=205,M=50005;
int n,m,k,s,t,U[M],V[M],C[M],D[M],pre[N],vis[N],f[M];
ll d[N],d0[N],d1[N],ans[M],ANS;
struct node1{
	int v,w,id;
};
vector<node1> e[2][N];//0：正边 1：反边 
void dij(int p,int S,int E,ll d[],int opt=0){//opt 是否有反向边 
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;++i) d[i]=0x3f3f3f3f3f3f3f3f;
	if (!p && !opt) memset(f,0,sizeof(f));
	d[S]=0;ll mi;int tmp;pre[S]=0;
	for (int i=1;i<=n;++i){
		mi=0x3f3f3f3f3f3f3f3f;
		for (int j=1;j<=n;++j)
			if (!vis[j] && d[j]<mi) mi=d[j],tmp=j;
		vis[tmp]=1;
		if (p==0 && V[opt]==tmp && d[U[opt]]>d[tmp]+C[opt]) 
			d[U[opt]]=d[tmp]+C[opt];
		if (p==1 && U[opt]==tmp && d[V[opt]]>d[tmp]+C[opt])
			d[V[opt]]=d[tmp]+C[opt];
		for (auto [v,w,id]:e[p][tmp])
			if (id!=opt && d[v]>d[tmp]+w) {
				d[v]=d[tmp]+w;
				if (!p && !opt) pre[v]=id;//更新最短路径树 
			}
	}
	if (!p && !opt) 
		for (int i=1;i<=n;++i) f[pre[i]]=1;
} 
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;++i){
		cin>>U[i]>>V[i]>>C[i]>>D[i];
		e[0][U[i]].push_back({V[i],C[i],i});
		e[1][V[i]].push_back({U[i],C[i],i}); 
	}
	dij(0,1,n,d0);
	dij(1,n,1,d1);
	ANS=d0[n];
	for (int i=1;i<=m;++i){
		if (f[i]) {
			dij(0,1,n,d,i);
			ans[i]=d[n];
		}
		else ans[i]=min(d0[n],d0[V[i]]+d1[U[i]]+C[i]);
	}
	dij(0,n,1,d0);
	dij(1,1,n,d1);
	ANS+=d0[1];
	for (int i=1;i<=m;++i){
		if (f[i]) {
			dij(0,n,1,d,i);
			ans[i]+=d[1]+D[i];
		}
		else ans[i]+=min(d0[1],d0[V[i]]+d1[U[i]]+C[i])+D[i];
		ANS=min(ANS,ans[i]);
	}
	cout<<(ANS>=0x3f3f3f3f3f3f3f3f?-1:ANS);
}