#include<bits/stdc++.h> using namespace std; #define int long long const int N=210,M=5e4+10; int n,m,ans[N],ansn[N],vis[N],ans2=1e9,vis2[M]; struct node{ int u,v,w,d,loc; }g[M]; struct node2{ int v,w; int f; }; struct node3{ int num,dis; bool operator<(const node3 &x)const{ return x.dis<dis; } }; priority_queue q; vector e[N],e2[N]; vector h; signed main(){ scanf("%lld %lld",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld %lld %lld %lld",&g[i].u,&g[i].v,&g[i].w,&g[i].d); g[i].loc=e[g[i].u].size(); e2[g[i].u].push_back({g[i].v,g[i].w,i}); } memset(ans,0x3f,sizeof(ans)); memset(vis,0,sizeof(vis)); ans[1]=0; q.push((node3){1,0}); while(!q.empty()){ int t=q.top().num; q.pop(); if(vis[t])continue; vis[t]=1; for(int j=0;j<e2[t].size();j++){ int v=e2[t][j].v,w=e2[t][j].w; if(ans[v]>ans[t]+w){ ans[v]=ans[t]+w; if(!vis[v]){ q.push((node3){v,ans[v]}); vis[e2[t][j].f]=1; } } } } memset(ans2,0x3f,sizeof(ans2)); memset(vis,0,sizeof(vis)); ans2[n]=0; q.push((node3){n,0}); while(!q.empty()){ int t=q.top().num; q.pop(); if(vis[t])continue; vis[t]=1; for(int j=0;j<e2[t].size();j++){ int v=e2[t][j].v,w=e2[t][j].w; if(ans2[v]>ans2[t]+w){ ans2[v]=ans2[t]+w; if(!vis[v]){ q.push((node3){v,ans2[v]}); vis[e2[t][j].f]=1; } } } } for(int i=1;i<=m;i++){ if(vis[i]){ h.push_back(g[i]); h[i].loc=e[g[i].u].size(); e[g[i].u].push_back({g[i].v,g[i].w,0}); } } for(int i=-1;i<h.size();i++){ int sum=h[i].d; if(i>=0){ e[h[i].u][h[i].loc].f=1; e[g[i].v].push_back({g[i].u,g[i].w,0}); }

	sum+=ans[1];
	ans2=min(ans2,sum);
	if(i>=1){
		e[g[i].u][g[i].loc].f=0;
		e[g[i].v].pop_back();
	}
}
if(ans2!=1e9)printf("%lld",ans2);
else cout<<-1;
return 0;

}