#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];
map<int,long long> dis[Max_N+5],vis[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);
		dis[E[i].u][i]=Inf,dis[E[i].v][i]=Inf;
	}
	for(int x=1;x<=n;x++){
		dis[x][-1]=Inf;
		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;
	} 
	Q.push(make_pair(0,B));
	dis[1][-1]=0;
	for(;Q.size();){
		int x=Q.top().second/B;
		int c=Q.top().second%B-1; Q.pop();
		if(vis[x][c]) continue; vis[x][c]=1;
		for(int i=lin[x];i;i=e[i].Next){
			if(c!=-1&&e[i].c<0&&E[c].c==E[-e[i].c].c){
				if(dis[x][c]+e[i].val-E[c].p<dis[e[i].Id][-1])
				 dis[e[i].Id][-1]=dis[x][c]+e[i].val-E[c].p,
				 Q.push(make_pair(-dis[e[i].Id][-1],e[i].Id*B));
			} else{
				if(dis[x][c]+e[i].val<dis[e[i].Id][max(e[i].c,-1)])
				 dis[e[i].Id][max(e[i].c,-1)]=min(dis[e[i].Id][max(e[i].c,-1)],dis[x][c]+e[i].val),
			     Q.push(make_pair(-dis[e[i].Id][max(e[i].c,-1)],e[i].Id*B+max(e[i].c,-1)+1));
			}
		}
	}
	long long ans=Inf;
	for(map<int,long long>::iterator It=dis[n].begin();It!=dis[n].end();++It)
	 ans=min(ans,(*It).second);
	printf("%lld\n",ans==Inf?-1:ans);
	return 0;
}