#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 8;
vector<vector<vector<pair<ll,ll>>>> g(N);
vector<vector<ll>> vv(N), sum(N), mn(N);
ll d[N];
bool vis[N];
void bfs(ll v){
// all except y of the same color, mn[col[y]], price[y]
memset(d, 0x3f, sizeof(d));
set<pair<ll,ll>> q;
d[v] = 0;
q.ins({0, v});
while(!q.empty()){
auto [dd, x] = *q.begin();
vis[x] = 1;
q.erase(q.begin());
if(dd != d[x]) continue;
for(ll i=0;i<(ll)vv[x].size();i++){
for(auto [p, to] : g[x][i]){
if(vis[to]) continue;
ll res = min(d[x] + min(p, sum[x][i] - p), mn[x][i] - p);
if(res < d[to]){
d[to] = res;
q.ins({d[to], to});
}
ll col = lower_bound(all(vv[to]), vv[x][i]) - vv[to].begin();
if(d[x] + p + sum[to][col] - p < mn[to][col]){
mn[to][col] = d[x] + p + sum[to][col] - p;
}
}
}
}
}
void solve() {
ll i, j;
ll n, m;
cin>>n>>m;
ll a[m], b[m], c[m], dd[m];
for(i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i]>>dd[i];
vv[a[i]].pb(c[i]);
vv[b[i]].pb(c[i]);
}
for(i=1;i<=n;i++){
sort(all(vv[i]));
vv[i].erase(unique(all(vv[i])), vv[i].end());
g[i].resize(vv[i].size());
sum[i].resize(vv[i].size());
mn[i].resize(vv[i].size(), inf);
}
for(i=0;i<m;i++){
ll low = lower_bound(all(vv[a[i]]), c[i]) - vv[a[i]].begin();
g[a[i]][low].pb({dd[i], b[i]});
sum[a[i]][low] += dd[i];
low = lower_bound(all(vv[b[i]]), c[i]) - vv[b[i]].begin();
g[b[i]][low].pb({dd[i], a[i]});
sum[b[i]][low] += dd[i];
}
bfs(1);
if(d[n] >= d[0]) cout<<-1<<endl;
else cout<<d[n]<<endl;
}
signed main(){
start();
ll t = 1;
//cin>>t;
while(t--) solve();
}
/*
*/
