#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("03")
#pragma GCC target("avx2")
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], id[MAXN];
vector<ll> dist[MAXN];
int qtd[MAXM], a[MAXM], b[MAXM], ida[MAXM], idb[MAXM], c[MAXM], p[MAXM]; ll tot[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++){
cin>>a[i]>>b[i]>>c[i]>>p[i];
adj[a[i]].push_back(b[i]); id[a[i]].push_back(i);
adj[b[i]].push_back(a[i]); id[b[i]].push_back(i);
ida[ i ] = sz(adj[a[i]]); idb[ i ] = sz(adj[b[i]]);
}
for(int i = 1; i <= n; i++){
dist[i].resize( sz(id[i])+1 );
dist[i][0] = INF;
for(int j = 1; j <= sz(id[i]); j++ )dist[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, lst = st.begin()->sc.sc; st.erase(st.begin());
if(v == n){ans = dist[v][lst]; break;}
for(int i = 0; i < sz(id[v]); i++){
int cor = c[ id[v][i] ]; ll preco = p[ id[v][i] ];
if(i != lst-1){ qtd[cor]++; tot[cor] += preco; }
}
for(int i = 0; i < sz(adj[v]); i++){
int viz = adj[v][i], cor = c[ id[v][i] ]; ll preco = p[ id[v][i] ];
if(qtd[ cor ] <= 1){
if(dist[viz][0] > dist[v][lst]){
st.erase( {dist[viz][0], {viz, 0} } );
dist[viz][0] = dist[v][lst];
st.insert( {dist[viz][0], {viz, 0} } );
}
}else{
if(dist[viz][0] > dist[v][lst] + tot[cor]-preco){
st.erase( {dist[viz][0], {viz, 0} } );
dist[viz][0] = dist[v][lst] + tot[cor]-preco;
st.insert( {dist[viz][0], {viz, 0} } );
}
}
int aux;
if(a[ id[v][i] ] == v)aux = idb[ id[v][i] ];
else aux = ida[ id[v][i] ];
if(dist[viz][aux] > dist[v][lst] + preco){
st.erase( {dist[viz][aux], {viz, aux} } );
dist[viz][aux] = dist[v][lst] + preco;
st.insert( {dist[viz][aux], {viz, aux} } );
}
}
for(int i = 0; i < sz(id[v]); i++){
qtd[ c[ id[v][i] ]] = 0; tot[ c[ id[v][i] ]] = 0;
}
}
if(ans == INF)cout<<"-1\n";
else cout<<ans<<"\n";
}
