#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0)
#define int long long
const int N = 1e5+10;
map<int,int> f2[N],d[N];
int f1[N],n,m;
struct edge
{
int to,c,w;
};
map<int,vector<edge> > ke[N];
main()
{
fasty;
//freopen("task.inp","r",stdin);
cin>>n>>m;
fori(i,1,m)
{
int u,v,w,c;
cin>>u>>v>>c>>w;
d[u][c]+=w;
d[v][c]+=w;
ke[u][c].pb({v,c,w});
ke[v][c].pb({u,c,w});
}
memset(f1,0x3f,sizeof(f1));
f1[1] = 0;
priority_queue<pair<int,ii> > h;
h.push({0,{1,0}});
//f2[umin][c] : (di vao u = c hoac di ra u cung = c)
while(!h.empty())
{
int dmin,umin,c;
tie(umin,c) = h.top().se;
dmin = -h.top().fi;
h.pop();
if(c)
{
if(f2[umin][c]!=dmin) continue;
forv(v,ke[umin][c])
{
if(f1[v.to] > dmin + d[umin][c] - v.w)
{
f1[v.to] = dmin + d[umin][c] - v.w;
h.push({-f1[v.to],{v.to,0}});
}
}
}
else
{
if(f1[umin]!=dmin) continue;
forv(i,ke[umin]) forv(j,i.se)
{
if(f1[j.to] > dmin + d[umin][j.c] - j.w)
{
f1[j.to] = dmin + d[umin][j.c] - j.w;
h.push({-f1[j.to],{j.to,0}});
}
if(f1[j.to] > dmin + j.w)
{
f1[j.to] = dmin + j.w;
h.push({-f1[j.to],{j.to,0}});
}
if(!f2[j.to].count(j.c) || (f2[j.to][j.c] > dmin))
{
f2[j.to][j.c] = dmin;
h.push({-f2[j.to][j.c],{j.to,j.c}});
}
}
}
}
cout<<(f1[n]==f1[0] ? -1 : f1[n]);
}
