#include <bits/stdc++.h>
using namespace std;
using ll=long long;
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'
constexpr int N=1e5+6;
constexpr ll INF=1e17;
priority_queue<tpl, vector<tpl>, greater<tpl>> pq;
vector<tpl> adj[N];
// ll odl[N];
map<int,ll> sum[N];
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) {
// for(int i=1; i<=n; i++) {
// odl[i]=INF;
// }
pq.push({0,0,w});
// odl[w]=0;
odl[w][0]=0;
while(!pq.empty()) {
ll ad; int k,a;
tie(k,ad,a)=pq.top();
pq.pop();
// if(ad!=odl[a]) continue;
if(ad!=get_odl(a,k)) continue;
each(e, adj[a]) {
ll p; int c,b;
tie(c,p,b)=e;
if(k==0) { // czy gdzies nie zamienilem (k,c)?
// 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 if(k==c) { // k!=0
// 0
ll cur=sum[a][c]-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;
rep(_, m) {
int a,b,c,p;
cin>>a>>b>>c>>p;
adj[a].pb({c,p,b});
adj[b].pb({c,p,a});
sum[a][c]+=p;
sum[b][c]+=p;
}
// for(int i=1; i<=n; i++) {
// cerr<<i<<'\n';
// each(cp, sum[i]) {
// cerr<<cp.first<<' '<<cp.second<<nl;
// }
// }
// cerr<<"===\n";
dij(1);
ll ans=get_odl(n,0);
// each(kv, odl[n]) {
// cerr<<kv.second<<' ';
// ans=min(ans,kv.second);
// }
// cerr<<nl;
if(ans==INF) {
cout<<"-1\n";
} else {
cout<<ans<<nl;
}
// cot(odl,1,n);
}
