#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> al;
typedef vector<ll> vl;
typedef pair<pl,pl> egg;
const ll INFL = 1e18;
const int MP = 220;
const int MN = 50500;
al g,h;
vector<vl> ha;
vector<egg> eg;
vl fist,rist;
vl fast,rast;
vl pis, ris;
vl so;
bitset<MN> fs,rs;
bitset<MP> fat,rat;
void dja(vl& w, vl& pa, int s) {
w.assign(g.size(),INFL);
pa.assign(g.size(),-1);
priority_queue<pl,vpl,greater<pl> > pq;
pq.push({0,s});
w[s] = 0;
while(!pq.empty()) {
pl co = pq.top();pq.pop();
int u = co.second;
if(co.first > w[u]) {continue;}
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
ll d = g[u][i].second;
if(d+w[u] < w[v]) {
w[v] = d+w[u];
int e = ha[u][i];
pa[v] = e;
pq.push({w[v],v});
}
}
}
}
void djb(vl& w, al& gr, int s) {
w.assign(gr.size(),INFL);
priority_queue<pl,vpl,greater<pl> > pq;
pq.push({0,s});
w[s] = 0;
while(!pq.empty()) {
pl co = pq.top();pq.pop();
int u = co.second;
if(co.first > w[u]) {continue;}
for(int i=0;i<gr[u].size();i++) {
int v = gr[u][i].first;
ll d = gr[u][i].second;
if(d+w[u] < w[v]) {
w[v] = d+w[u];
pq.push({w[v],v});
}
}
}
}
void pre() {
dja(fist,pis, 0);
dja(rist,ris, g.size()-1);
djb(fast,h,g.size()-1);
djb(rast,h,0);
int pp = g.size()-1;
while(pis[pp] != -1) {
fat.set(pp);
fs.set(pis[pp]);
pp = eg[pis[pp]].first.first;
}
fat.set(0);
for(int i=0;i<ris.size();i++) {
if(ris[i] != -1) {
rs.set(ris[i]);
}
}
pp = 0;
while(ris[pp] != -1) {
rat.set(pp);
rs.set(ris[pp]);
pp = eg[ris[pp]].first.first;
}
rat.set(g.size()-1);
}
ll proc(int e) {
vl tp;
int u = eg[e].first.first;
int v = eg[e].first.second;
ll ex = eg[e].second.second;
ll reg = eg[e].second.first;
int eid = so[e];
ll fdi,rdi;
if(fs[e]) {
g[u][eid].second = INFL;
g[v].push_back({u,reg});
djb(tp,g,0);
fdi = tp[g.size()-1];
g[v].pop_back();
g[u][eid].second = reg;
} else {
fdi = fist[g.size()-1];
fdi = min(fdi,fist[v]+fast[u]+reg);
}
if(rs[e]) {
g[u][eid].second = INFL;
g[v].push_back({u,reg});
djb(tp,g,g.size()-1);
rdi = tp[0];
g[v].pop_back();
g[u][eid].second = reg;
} else {
rdi = rist[0];
rdi = min(rdi,rist[v]+rast[u]+reg);
}
return fdi+rdi+ex;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n,m;
cin >> n >> m;
g.assign(n,vpl());
h.assign(n,vpl());
ha.assign(n,vl());
fist.assign(n,INFL);
rist.assign(n,INFL);
for(int i=0;i<m;i++) {
ll a,b,c,d;
cin >> a >> b >> c >> d;
a--;b--;
so.push_back(g[a].size());
g[a].push_back({b,c});
h[b].push_back({a,c});
ha[a].push_back(i);
eg.push_back({{a,b},{c,d}});
}
pre();
ll res = fist[n-1]+rist[0];
for(int i=0;i<m;i++) {
res = min(res,proc(i));
}
if(res >= INFL) {
cout << -1 << '\n';
} else {
cout << res << '\n';
}
}
