#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=2e5,B=1e6;
const long long Inf=1e18;
int n,m,Num,lin[Max_N+5];
long long sum[Max_M+5],dis[2][Max_N+5],vis[2][Max_N+5];
struct Edge_fir{ int u,v,c,p; } E[Max_M+5];
vector<int> a[Max_N+5];
priority_queue< pair< long long, long long > > Q;
struct Edge{
	int Next,Id,c;
	long long val;
} e[Max_M*8+5];
void Insert(int x,int y,int c,long long w){
	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y; e[Num].c=c; e[Num].val=w;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].c,&E[i].p);
		a[E[i].u].push_back(i),a[E[i].v].push_back(i);
	}
	for(int x=1;x<=n;x++){
		for(int i=0;i<a[x].size();i++)
		 sum[E[a[x][i]].c]+=E[a[x][i]].p;
		for(int i=0;i<a[x].size();i++)
		 Insert(x,x^E[a[x][i]].v^E[a[x][i]].u,a[x][i],E[a[x][i]].p),
		 Insert(x,x^E[a[x][i]].v^E[a[x][i]].u,-a[x][i],sum[E[a[x][i]].c]-E[a[x][i]].p);
		for(int i=0;i<a[x].size();i++)
		 sum[E[a[x][i]].c]-=E[a[x][i]].p;
	} 
	for(int i=0;i<=2;i++)
	 for(int j=1;j<=max(n,m);j++)
	  dis[i][j]=Inf;
	Q.push(make_pair(0,-1+n)); dis[2][1]=0;
	for(;Q.size();){
		int c=Q.top().second/B; 
		int op=Q.top().second%B-n; Q.pop();
		if(op<0) {
			int x=-op;
			if(vis[2][x]) continue; vis[2][x]=1;
			for(int i=lin[x];i;i=e[i].Next){
				if(e[i].c<0){
					int To=x^E[-e[i].c].u^E[-e[i].c].v;
					if(dis[2][x]+e[i].val<dis[2][To])
					 dis[2][To]=dis[2][x]+e[i].val,
					 Q.push(make_pair(-dis[2][To],-To+n));
				} else {
					int np=x==E[e[i].c].u?1:0;
					if(dis[2][x]+e[i].val<dis[np][e[i].c])
					 dis[np][e[i].c]=dis[2][x]+e[i].val,
					 Q.push(make_pair(-dis[np][e[i].c],1ll*e[i].c*B+np+n));
				}
			}
		} else {
			if(vis[op][c]) continue; vis[op][c]=1;
			int x=op?E[c].v:E[c].u;
			for(int i=lin[x];i;i=e[i].Next){
				if(e[i].c<0){
					int To=x^E[-e[i].c].u^E[-e[i].c].v;
					if(dis[op][c]+e[i].val-E[c].p<dis[2][To])
					 dis[2][To]=dis[op][c]+e[i].val-E[c].p,
					 Q.push(make_pair(-dis[2][To],-To+n));
				} else {
					int np=x==E[e[i].c].u?1:0;
					if(dis[op][x]+e[i].val<dis[np][e[i].c])
					 dis[np][e[i].c]=dis[op][x]+e[i].val,
					 Q.push(make_pair(-dis[np][e[i].c],1ll*e[i].c*B+np+n));
				}
			}
		}
	}
	long long ans=dis[2][n];
	for(int i=1;i<=m;i++)
	 if(E[i].u==n) ans=min(ans,dis[0][i]);
	 else if(E[i].v==n) ans=min(ans,dis[1][i]);
	printf("%lld\n",ans==Inf?-1:ans);
	return 0;
}