// Code by khongbietdatgi
// Link chấm:
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define pb push_back
#define pli pair<long long,int>
#define pll pair<long long, long long>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pii pair<int,int>
#define task "TEST"
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define frr(i,a,b) for(int i=a;i>=b;i--)
#define piii pair<int,pii>
#define plii pair<ll,pii>
const long long INF = 1e18 ;
const int inf = 1e9 ;
const int maxn = 200005;
const int mod = 1e9+7;
int n,m;
int u[maxn], v[maxn], c[maxn];
ll p[maxn];
ll d[maxn];
char ku[maxn], kv[maxn];
vector<pii> adj[maxn];
void doc(){
cin >> n >> m;
fr(i,1,m){
cin >> u[i] >> v[i] >> c[i] >> p[i];
adj[u[i]].pb({c[i], i});
adj[v[i]].pb({c[i], i});
}
fr(i,1,n){
sort(adj[i].begin(), adj[i].end());
for(int j = 0; j < (int)adj[i].size(); ){
int k = j;
while(k < (int)adj[i].size() && adj[i][k].fi == adj[i][j].fi) k++;
if(k - j == 1){
int id = adj[i][j].se;
if(u[id] == i) ku[id] = 1;
else kv[id] = 1;
}
j = k;
}
}
}
void solve(){
fr(i,1,n) d[i] = INF;
priority_queue<pll, vector<pll>, greater<pll>> q;
d[1] = 0;
q.push({0,1});
while(q.size()){
auto it = q.top(); q.pop();
ll du = it.fi;
int x = it.se;
if(du != d[x]) continue;
for(auto e : adj[x]){
int id = e.se;
int y = (u[id] == x ? v[id] : u[id]);
ll w = (u[id] == x ? (ku[id] ? 0 : p[id]) : (kv[id] ? 0 : p[id]));
if(d[y] > du + w){
d[y] = du + w;
q.push({d[y], y});
}
}
}
if(d[n] == INF) cout << -1;
else cout << d[n];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
int test=1;
//cin>>test;
fr(i,1,test){
doc();
solve();
}
}
