#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=2e5+3;
struct bst {
int lb,lsb,rb,rsb;
ll ls,rs;
};
struct item {
ll w;
int u,idx;
bool operator < (const item oth) const {
return w>oth.w;
}
};
struct edge {
int u,v,w,c;
};
map<pair<int,int>,ll> d;
map<ll,int> b,sb;
map<ll,ll> sm;
int n,m;
edge e[N];
vector<int> g[N];
bst bb[N];
priority_queue<item> pq;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
For(i,1,m) {
cin >> e[i].u >> e[i].v >> e[i].c >> e[i].w;
g[e[i].u].pb(i);
g[e[i].v].pb(i);
}
For(i,1,n) {
b.clear(),sb.clear(),sm.clear();
for(auto el: g[i]) {
sm[e[el].c]+=e[el].w;
if (!b.count(e[el].c)) b[e[el].c]=el;
else {
if (e[b[e[el].c]].w<e[el].w) {
sb[e[el].c]=b[e[el].c];
b[e[el].c]=el;
} else if (!sb.count(e[el].c) || e[sb[e[el].c]].w<e[el].w) {
sb[e[el].c]=el;
}
}
}
for(auto el: g[i]) {
// if (i==3) debug(b[4]);
if (e[el].u==i) {
bb[el].lb=b[e[el].c];
bb[el].lsb=sb[e[el].c];
bb[el].ls=sm[e[el].c];
} else {
bb[el].rb=b[e[el].c];
bb[el].rsb=sb[e[el].c];
bb[el].rs=sm[e[el].c];
}
}
}
pq.push({0,1,-1});
d[{1,-1}]=0;
// debug(bb[3].rb);
while(sz(pq)) {
ll w=pq.top().w;
int u=pq.top().u,idx=pq.top().idx;
pq.pop();
// debug(w,u,idx);
if (d[{u,idx}]!=w) continue;
if (idx==-1) {
for(auto i: g[u]) {
int v=(e[i].u==u?e[i].v:e[i].u);
if (!d.count({v,i}) || d[{v,i}]>w+e[i].w) {
d[{v,i}]=e[i].w+w;
pq.push({e[i].w+w,v,i});
}
ll ww=0;
if (e[i].u==u) ww=bb[i].ls-e[i].w;
else ww=bb[i].rs-e[i].w;
if (!d.count({v,-1}) || d[{v,-1}]>ww+w) {
d[{v,-1}]=w+ww;
pq.push({w+ww,v,-1});
}
}
} else {
if (!d.count({u,-1}) || d[{u,-1}]>w) {
d[{u,-1}]=w;
pq.push({w,u,-1});
}
int s1,s2;
if (e[idx].u==u) {
s1=bb[idx].lb;
s2=bb[idx].lsb;
} else {
s1=bb[idx].rb;
s2=bb[idx].rsb;
}
if (s1!=idx) {
int v=(e[s1].u==u?e[s1].v:e[s1].u);
ll ww=(e[s1].u==u?bb[s1].ls:bb[s1].rs);
ww-=e[idx].w+e[s1].w;
if (!d.count({v,s1}) || d[{v,s1}] > ww+w) {
d[{v,s1}]=ww+w;
pq.push({ww+w,v,s1});
}
} else if (s2!=0) {
int v=(e[s2].u==u?e[s2].v:e[s2].u);
ll ww=(e[s2].u==u?bb[s2].ls:bb[s2].rs);
ww-=e[idx].w+e[s2].w;
if (!d.count({v,s2}) || d[{v,s2}] > ww+w) {
d[{v,s2}]=ww+w;
pq.push({ww+w,v,s2});
}
}
}
}
ll ans=1e18;
for(auto el: d)
if (el.ff.ff==n) ans=min(ans,el.ss);
if (ans>=1e18) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
