#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pr=pair<ll,int>; // odl, wie
using tpl=tuple<int,ll,int>; // kolor, odl, wie
#define nl '\n'
#define pb push_back
#define sz(x) (int)(x).size()
#define each(a, b) for(const auto& a:b)
#define rep(a, b) for(int a=0; a<(b); a++)
#define coz(x) cerr<<(#x)<<": "<<(x)<<'\n'
#define cot(x, l, n) cerr<<(#x)<<": "; \
for(int i=l; i<l+n; i++) { cerr<<x[i]<<' '; } cerr<<'\n'
inline int ri() {
int x=0;
char ch=getchar_unlocked();
while (ch<'0' || ch>'9') {
ch=getchar_unlocked();
}
while (ch>='0' && ch<='9') {
x=x*10+(ch-'0');
ch=getchar_unlocked();
}
return x;
}
constexpr int N=1e5+6;
constexpr ll INF=1e17;
auto cmp=[](const tpl& a, const tpl& b) {
return get<1>(a)>get<1>(b);
};
priority_queue<tpl, vector<tpl>, decltype(cmp)> pq(cmp);
vector<tpl> adj[N];
unordered_map<int,vector<pr>> col[N];
// ll odl[N];
unordered_map<int,ll> sum[N];
unordered_map<int,ll> odl[N];
int n,m;
ll get_odl(int w, int c) {
auto iter=odl[w].find(c);
if(iter==odl[w].end()) return INF;
return iter->second;
}
void dij(int w) {
pq.push({0,0,w});
odl[w][0]=0;
while(!pq.empty()) {
ll ad; int k,a;
tie(k,ad,a)=pq.top();
pq.pop();
if(ad!=get_odl(a,k)) continue;
if(k==0) {
each(e, adj[a]) {
ll p; int c,b;
tie(c,p,b)=e;
// c
ll alt=ad;
if(alt<get_odl(b,c)) {
odl[b][c]=alt;
pq.push({c,odl[b][c],b});
}
// 0
ll cur=min(sum[a][c]-p, p)+ad;
if(cur<get_odl(b,0)) {
odl[b][0]=cur;
pq.push({0,odl[b][0],b});
}
}
} else { // k!=0
auto iter=col[a].find(k);
if(iter==col[a].end()) continue;
each(e, col[a][k]) {
// 0
ll p; int b;
tie(p,b)=e;
ll cur=sum[a][k]-p+ad;
if(cur<get_odl(b,0)) {
odl[b][0]=cur;
pq.push({0,odl[b][0],b});
}
}
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
// cin>>n>>m;
n=ri(); m=ri();
rep(_, m) {
int a,b,c,p;
// cin>>a>>b>>c>>p;
a=ri(); b=ri(); c=ri(); p=ri();
adj[a].pb({c,p,b});
adj[b].pb({c,p,a});
col[a][c].pb({p,b});
col[b][c].pb({p,a});
sum[a][c]+=p;
sum[b][c]+=p;
}
dij(1);
ll ans=get_odl(n,0);
if(ans==INF) {
cout<<"-1\n";
} else {
cout<<ans<<nl;
}
}
