#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
typedef long long ll;
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
ll min(ll a,ll b){
	return a<b?a:b;
}
const int maxn=100005,maxm=200005;
int n,m,k,u,v,c,w;
ll S[maxn+maxm*2],dis[maxn+maxm*2];
int head[maxn+maxm*2],total;
struct Edge{
	int to,next,c,w;
}e[maxm*4];
std::map<int,int>virt[maxn+maxm*2];
void add(int u,int v,int c,int w){
	if(!virt[u].count(c)){
		virt[u][c]=++k;
		e[++total]={k,head[u],0,0};
		head[u]=total;
	}
	int t=virt[u][c];
	e[++total]={v,head[t],c,w};
	head[t]=total;
	S[t]+=w;
}
struct Node{
	int u;
	ll d;
};
bool operator<(Node a,Node b){
	return a.d!=b.d?a.d>b.d:a.u<b.u;
}
std::priority_queue<Node>q;
void update(int u,ll d){
	if(dis[u]>d){
		dis[u]=d;
		q.push(Node{u,d});
	}
}
void dijkstra(){
	q.push(Node{1,dis[1]=0});
	while(!q.empty()){
		int u=q.top().u;
		ll d=q.top().d;
		q.pop();
		if(dis[u]<d)continue;
		if(u<=n){
			if(dis[u]<=d)continue;
			for(int i=head[u];i;i=e[i].next){
				int v=e[i].to;
				for(int j=head[v];j;j=e[j].next){
					update(e[j].to,d+min((ll)e[j].w,S[v]-e[j].w));
					update(virt[e[j].to][e[j].c],d);
				}
			}
		}else
			for(int i=head[u];i;i=e[i].next){
				int v=e[i].to;
				update(v,d+S[u]-e[i].w);
			}
	}
}
int main(){
	n=k=read(),m=read();
	for(int i=1;i<=m;i++){
		u=read(),v=read(),c=read(),w=read();
		add(u,v,c,w),add(v,u,c,w);
	}
	memset(dis,63,sizeof(dis));
	dijkstra();
	printf("%lld\n",dis[n]<0x3f3f3f3f3f3f3f3f?dis[n]:-1ll);
	return 0;
}