#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];
map<int, ll> dist[MAXN];
int qtd[MAXM], c[MAXN], p[MAXN]; 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++){
int a,b; cin>>a>>b>>c[i]>>p[i];
adj[a].push_back(b); id[a].push_back(i);
adj[b].push_back(a); id[b].push_back(i);
}
for(int i = 1; i <= n; i++){
dist[i][0] = INF;
for(int j = 0; j < sz(id[i]); j++ )dist[i][ id[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());
ll d = dist[v][a];
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(id[v][i] != a){ 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(d0 > d){
st.erase( {d0, {viz, 0} } );
dist[viz][0] = d;
st.insert( {d, {viz, 0} } );
}
}else{
if(d0 > d + tot[cor]-preco){
st.erase( {d0, {viz, 0} } );
dist[viz][0] = d + tot[cor]-preco;
st.insert( {d, {viz, 0} } );
}
}
ll did = dist[viz][id[v][i]];
if(did > d + preco){
st.erase( {did, {viz, id[v][i]} } );
dist[viz][id[v][i]] = d + preco;
st.insert( {d + preco, {viz, id[v][i]} } );
}
}
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";
}
