#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=2e5;
const long long Inf=1e18; 
int n,m,Num,Node,lin[(Max_N<<1)+5],vis[(Max_N<<1)+5];
long long dis[(Max_N<<1)+5];
map<int,int> mp[Max_N+5];
map<int,long long> sum[Max_N+5];
priority_queue< pair<long long,int> > Q;
struct EDGE{ int u,v,c,p; } E[Max_M+5];
struct Edge{
	int Id,Next;
	long long w;
} e[Max_M*8+5];
void Insert(int x,int y,long long w){
	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y; e[Num].w=w;
}
int main(){
	scanf("%d%d",&n,&m); Node=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].c,&E[i].p);
		sum[E[i].u][E[i].c]+=E[i].p;
		sum[E[i].v][E[i].c]+=E[i].p;
		if(!mp[E[i].u][E[i].c]) mp[E[i].u][E[i].c]=++Node;
		if(!mp[E[i].v][E[i].c]) mp[E[i].v][E[i].c]=++Node;
	}
	for(int i=1;i<=m;i++){
		Insert(E[i].u,E[i].v,E[i].p);
		Insert(E[i].u,E[i].v,sum[E[i].u][E[i].c]-E[i].p);
		Insert(E[i].u,mp[E[i].v][E[i].c],0);
		Insert(mp[E[i].u][E[i].c],E[i].v,sum[E[i].u][E[i].c]-E[i].p);
		Insert(E[i].v,E[i].u,E[i].p);
		Insert(E[i].v,E[i].u,sum[E[i].v][E[i].c]-E[i].p);
		Insert(E[i].v,mp[E[i].u][E[i].c],0);
		Insert(mp[E[i].v][E[i].c],E[i].u,sum[E[i].u][E[i].c]-E[i].p);
	}
	for(int i=1;i<=Node;i++) dis[i]=Inf;
	dis[1]=0; Q.push(make_pair(0,1));
	for(;Q.size();){
		int x=Q.top().second; Q.pop();
		if(vis[x]) continue; vis[x]=1;
		for(int i=lin[x];i;i=e[i].Next)
		 if(dis[x]+e[i].w<dis[e[i].Id]){
		 	dis[e[i].Id]=dis[x]+e[i].w;
		 	Q.push(make_pair(-dis[e[i].Id],e[i].Id));
		 }
	}
	printf("%lld\n",dis[n]==Inf?-1:dis[n]);
	return 0;
}