#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 1e5+5, MAXM = 2*1e5+5;
const ll INF = 1e15;
vector<int> adj[MAXN], c[MAXN], p[MAXN];
map<int, ll> dist[MAXN];
int qtd[MAXM];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m; cin>>n>>m;
for(int i = 1; i <= m; i++){
int a,b,x,y; cin>>a>>b>>x>>y;
adj[a].push_back(b); c[a].push_back(x); p[a].push_back(y);
adj[b].push_back(a); c[b].push_back(x); p[b].push_back(y);
}
for(int i = 1; i <= n; i++){
dist[i][0] = INF;
for(int j = 0; j < sz(c[i]); j++ )dist[i][ c[i][j] ] = INF;
}
set< pair<ll, pair<int,int> > > st;
dist[1][0] = 0; st.insert( {0, {1,0} } );
ll ans = INF;
while(!st.empty()){
int v = st.begin()->sc.fi, a = st.begin()->sc.sc; st.erase(st.begin());
if(v == n)ans = min(ans, dist[v][a] );
for(int x : c[v]) qtd[x]++;
if(a > 0)qtd[ a ]--;
for(int i = 0; i < sz(adj[v]); i++){
int viz = adj[v][i], cor = c[v][i], preco;
if(qtd[ cor ] <= 1)preco = 0;
else preco = p[v][i];
if(preco == 0 && dist[viz][0] > dist[v][a]){
st.erase( {dist[viz][0], {viz, 0} } );
dist[viz][0] = dist[v][a];
st.insert( {dist[viz][0], {viz, 0} } );
}
if(preco > 0 && dist[viz][cor] > dist[v][a] + preco){
st.erase( {dist[viz][cor], {viz, cor} } );
dist[viz][cor] = dist[v][a] + preco;
st.insert( {dist[viz][cor], {viz, cor} } );
}
}
for(int x : c[v]) qtd[x] = 0;
}
if(ans == INF)cout<<"-1\n";
else cout<<ans<<"\n";
}
