#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
#define vt vector
#define ar array
#define pr pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define fr(i,a,b) for(int i = a; i < b; ++i)
#define rf(i,a,b) for(int i = b-1; i >= a; --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace IN{
template<class T> void re(vector<T> &A);
template<class S,class T> void re(pair<S,T> &A);
template<class T,size_t N> void re(array<T,N> &A);
template<class T> void re(T& x){
cin >> x;}
template<class H, class... T> void re(H& h, T&... t){
re(h); re(t...);}
template<class T> void re(vector<T> &A){
for(auto& x : A) re(x);}
template<class S,class T> void re(pair<S,T> &A){
re(A.first); re(A.second);}
template<class T,size_t N> void re(array<T,N> &A){
for(int i = 0; i < N; ++i) re(A[i]);}
}
namespace OUT{
template<class T>
void __p(const T& a){ cout<<a; }
template<class T, class F>
void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
template<class T, size_t N>
void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
template<class T>
void __p(const vector<T>& a){
cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
template<class T, class ...Arg>
void __p(T a1, Arg ...a){__p(a1); __p(a...); }
template<class Arg1>
void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
template<class Arg1, class ... Args>
void __f(const char *ss, Arg1 &&arg1, Args &&... args){
int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
#define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
}
namespace FUN{
void IO(string s = ""){
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
if(!s.empty()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time(){
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time-start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
template<class T> bool ckmin(T& a, const T& b){
return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, const T& b){
return a < b ? a = b, true : false; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int L, int R){
return uniform_int_distribution<int>(L,R)(rng); }
template<class T> int sz(const T& x){
return int(x.size()); }
template<class T> int lb(const vector<T>& vec,const T& val){
return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }
template<class T> int ub(const vector<T>& vec,const T& val){
return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }
constexpr int dx[4] = {1,0,-1,0};
constexpr int dy[4] = {0,1,0,-1};
constexpr char dr[4] = {'D','R','U','L'};
constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
constexpr int INF = 2e9;
template<class T>
vector<T> V(int n,T val){
return vector<T> (n,val);
}
template<class T>
vector<vector<T>> V(int n,int m,T val){
return vector<vector<T>> (n,vector<T> (m,val));
}
template<class T>
vector<vector<vector<T>>> V(int n,int m,int k,T val){
return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
}
}
using namespace IN;
using namespace OUT;
using namespace FUN;
struct E{
int to,c,p;
};
signed main(){
IO();
int n,m;
re(n,m);
vt<vt<E>> g(n);
fr(e,0,m){
int u,v,c,p;
re(u,v,c,p);
--u,--v,--c;
g[u].pb({v,c,p});
g[v].pb({u,c,p});
}
vt<vt<E>> g_new = g;
fr(i,0,n){
sort(all(g[i]),[&](auto l,auto r){
return l.c == r.c ? l.p < r.p : l.c < r.c;
});
for(int l = 0, r = 0; l < sz(g[i]); l = r + 1, r = l){
while(r < sz(g[i]) && g[i][r].c == g[i][l].c)
++r;
if(r - l <= 1)
continue;
int tot = 0;
for(int k = l; k < r; ++k){
tot += g[i][k].p;
if(k > l)
assert(g[i][k].c == g[i][k-1].c);
}
for(int p = l; p < r; ++p){
for(int q = p + 1; q < r; ++q){
g_new[g[i][p].to].pb({g[i][q].to,-1,min(tot-g[i][p].p,tot-g[i][q].p)});
g_new[g[i][q].to].pb({g[i][p].to,-1,min(tot-g[i][p].p,tot-g[i][q].p)});
}
}
// for(int k = l; k < r - 1; ++k){
// g_new[g[i][k].to].pb({g[i][r-1].to,-1,min(tot-g[i][k].p,tot-g[i][r-1].p)});
// g_new[g[i][r-1].to].pb({g[i][k].to,-1,min(tot-g[i][k].p,tot-g[i][r-1].p)});
// }
}
}
vt<int> sum(m,0);
auto upd = [&](int i) -> void {
for(auto edge : g_new[i])
if(edge.c >= 0)
sum[edge.c] = 0;
for(auto edge : g_new[i])
if(edge.c >= 0)
sum[edge.c] += edge.p;
};
vt<int> dis(n,INFLL1);
priority_queue<ar<int,2>> pq;
dis[0] = 0;
pq.push({-dis[0],0});
while(!pq.empty()){
auto [d,i] = pq.top(); pq.pop();
d *= -1;
if(d != dis[i])
continue;
upd(i);
for(auto edge : g_new[i]){
if(edge.c >= 0){
if(ckmin(dis[edge.to],dis[i] + min(edge.p,sum[edge.c] - edge.p)))
pq.push({-dis[edge.to],edge.to});
}else{
if(ckmin(dis[edge.to],dis[i] + edge.p))
pq.push({-dis[edge.to],edge.to});
}
}
}
cout << (dis[n-1] == INFLL1 ? int(-1) : dis[n-1]);
// output_run_time();
return 0;
}
