#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define mk make_pair
const int MAXN = 1e5+10 ;
const int MAXM = 2e5+10 ;
const ll inf = 1e18+10LL ;
using namespace std ;
int N , M ;
int cor[MAXM*2] ;
int j[MAXM*2] ;
ll p[MAXM*2] ;
map< pair<int, int> , ll > custo ;
map< pair<int,int> , int > chave ;
vector<int> adj[MAXN] ;
vector<pair<int,ll> > graph[MAXM+MAXN] ;
void add(pair<int,int> par , ll val ){
if(custo.find(par) == custo.end()) custo[par] = 0 ;
custo[par] += val ;
}
int main()
{
ios_base::sync_with_stdio(false) ;
cin.tie(0) ;
cin >> N >> M ;
for(int i = 0 , a , b ; i < 2*M ; i += 2 ){
cin >> a >> b >> cor[i] >> p[i] ;
j[i] = b ;
j[i+1] = a ;
cor[i+1] = cor[i] ;
p[i+1] = p[i] ;
add( mk(a,cor[i]) , p[i] ) ;
add( mk(b,cor[i]) , p[i] ) ;
chave[mk(a,cor[i])] = chave[mk(b,cor[i])] = 0 ;
adj[a].push_back(i) ;
adj[b].push_back(i+1) ;
}
for(int i = 1 ; i <= N ; i++ ) chave[mk(i,0)] = 0 ;
int Key = 0 ;
for(auto &e : chave ) e.second = ++Key ;
for(int i = 1 ; i <= N ; i++ ){
int x = chave[mk(i,0)] ;
for(auto e : adj[i] ){
int y = chave[mk(i,cor[e])] ;
int a = chave[mk(j[e],0)] ;
int b = chave[mk(j[e],cor[e])] ;
graph[a].push_back( make_pair( y , custo[mk(i,cor[e])] - p[e] ) ) ;
graph[b].push_back( make_pair( x, 0 ) ) ;
graph[a].push_back( make_pair( x, p[e] ) ) ;
}
}
for(auto e : chave )
if(e.first.second) graph[ e.second ].push_back( mk( chave[mk(e.first.first,0)], 0 ) ) ;
vector<ll> dist(Key+1, inf ) ;
int T = chave[ mk(N,0) ] ;
priority_queue<pair<ll,int> , vector<pair<ll,int> > , greater<pair<ll,int> > > fila ;
fila.push( mk( dist[T] = 0 , T ) ) ;
while(!fila.empty()){
int x = fila.top().second ;
ll d = fila.top().first ;
fila.pop() ;
if(d != dist[x]) continue ;
for(auto e : graph[x]){
ll newD = d + e.second ;
int viz = e.first ;
if(newD >= dist[viz]) continue ;
fila.push( make_pair(dist[viz] = newD , viz) ) ;
}
}
int S = chave[ mk(1,0) ] ;
if(dist[S] == inf ) dist[S] = -1 ;
cout << dist[S] << "\n" ;
}
