#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], 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;
}
priority_queue< pair<ll, pair<int,int> > > pq;
dist[1][0] = 0; pq.push( {0, {1,0} } );
ll ans = INF;
while(!pq.empty()){
int v = pq.top().sc.fi, lst = pq.top().sc.sc;
if(pq.top().fi != dist[v][lst]){pq.pop(); continue;}
pq.pop();
ll d = dist[v][lst];
if(v == n)ans = min(ans, d );
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] ];
ll d0 = dist[viz][0];
if(qtd[ cor ] <= 1){
if(dist[viz][0] > d){
dist[viz][0] = d;
pq.push( {dist[viz][0], {viz, 0} } );
}
}else{
if(dist[viz][0] > d + tot[cor]-preco){
dist[viz][0] = d + tot[cor]-preco;
pq.push( {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] > d + preco){ dist[viz][aux] = d + preco;
pq.push( {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";
}
