#include<bits/stdc++.h>
#define MAX 1000005
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
const ll inf=1e18;
int n,m;
int head[MAX],ver[MAX<<1],nxt[MAX<<1],len[MAX<<1],col[MAX<<1],cnt;
void add(int a,int b,int c,int d){
	ver[++cnt]=b,col[cnt]=d,len[cnt]=c,nxt[cnt]=head[a],head[a]=cnt;
}
vector<pll> e[MAX],hv[MAX];
int st[MAX],top,vis[MAX],tot;
ll dis[MAX];
void dijkstra(){
	for(int i=1;i<=tot;i++) dis[i]=inf,vis[i]=0;
	priority_queue<pll> q;
	dis[1]=0;
	q.push(mkp(0,1));
	while(!q.empty()){
		int now=q.top().second;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=0;i<e[now].size();i++){
			int to=e[now][i].fi;
			ll len=e[now][i].se;
			if(dis[to]>dis[now]+len){
				dis[to]=dis[now]+len;
				q.push(mkp(-dis[to],to));
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);tot=n;
	for(int i=1,a,b,c,d;i<=m;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		add(a,b,d,c),add(b,a,d,c);
		e[a].pb(mkp(b,d));e[b].pb(mkp(a,d));
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nxt[j]){
			int to=ver[j],c=col[j];
			if(!vis[c]) st[++top]=c;
			hv[c].pb(mkp(to,len[j]));
		}
		for(int j=1;j<=top;j++){
			int c=st[j];
			ll sum=0;
			for(int k=0;k<hv[c].size();k++)
				sum+=hv[c][k].se;
			tot++;e[i].pb(mkp(tot,0));
			for(int k=0;k<hv[c].size();k++)
				e[tot].pb(mkp(hv[c][k].fi,sum-hv[c][k].se)),e[hv[c][k].fi].pb(mkp(tot,0));
			hv[c].clear();
		}
		top=0;
	}
	dijkstra();
	if(dis[n]==inf) printf("-1");
	else printf("%lld",dis[n]);
}