#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7, INF=2e9+7, K=14;
pair<int,int>xd={INF, INF};
vector<int>V[207], S[207];
pair<pair<int,int>,pair<int,int>>kraw[LIM];
int odl[207][4], wazne[LIM], n, m;
pair<int,int>blok[210], mi[210];
void dodaj(int v, pair<int,int>x) {
mi[v]=min(mi[v], x);
blok[v/K]=min(blok[v/K], x);
}
pair<pair<int,int>,int>znajdz() {
pair<pair<int,int>,int>p={xd, INF};
rep(i, K+1) p=min(p, {blok[i], i});
pair<int,int>ans=xd;
rep(i, K) ans=min(ans, mi[p.nd*K+i]);
blok[p.nd]=xd;
rep(i, K) if(mi[p.nd*K+i]==ans) {
mi[p.nd*K+i]=xd;
return {ans, p.nd*K+i};
}
}
void dijkstra(int v, int f, int z) {
rep(i, 210) {
odl[i][f]=INF;
blok[i]=mi[i]=xd;
}
dodaj(v, {0, -1});
while(true) {
pair<pair<int,int>,int>p=znajdz();
if(p.st==xd) return;
if(z && p.st.nd!=-1) wazne[p.st.nd]=1;
odl[p.nd][f]=p.st.st;
for(auto i : V[p.nd]) if(kraw[i].st.st==p.nd && odl[kraw[i].st.nd][f]==INF) {
dodaj(kraw[i].st.nd, {odl[p.nd][f]+kraw[i].nd.st, i});
}
}
}
void dijkstras(int v, int f, int z) {
rep(i, n) {
odl[i][f]=INF;
blok[i]=mi[i]=xd;
}
dodaj(v, {0, -1});
while(true) {
pair<pair<int,int>,int>p=znajdz();
if(p.st==xd) return;
if(z && p.st.nd!=-1) wazne[p.st.nd]=1;
odl[p.nd][f]=p.st.st;
for(auto i : S[p.nd]) if(odl[kraw[i].st.st][f]==INF) {
dodaj(kraw[i].st.st, {odl[p.nd][f]+kraw[i].nd.st, i});
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, m) {
cin >> kraw[i].st.st >> kraw[i].st.nd >> kraw[i].nd.st >> kraw[i].nd.nd;
--kraw[i].st.st; --kraw[i].st.nd;
V[kraw[i].st.st].pb(i);
S[kraw[i].st.nd].pb(i);
}
dijkstra(0, 0, 1);
dijkstras(n-1, 1, 1);
dijkstra(n-1, 2, 1);
dijkstras(0, 3, 1);
int ans=INF;
if(odl[n-1][0]<INF && odl[0][2]<INF) ans=min(ans, odl[n-1][0]+odl[0][2]);
rep(i, m) if(!wazne[i]) {
int p1=odl[n-1][0], p2=odl[0][2];
if(odl[kraw[i].st.nd][0]<INF && odl[kraw[i].st.st][1]<INF) {
p1=min(p1, odl[kraw[i].st.nd][0]+odl[kraw[i].st.st][1]+kraw[i].nd.st);
}
if(odl[kraw[i].st.nd][2]<INF && odl[kraw[i].st.st][3]<INF) {
p2=min(p2, odl[kraw[i].st.nd][2]+odl[kraw[i].st.st][3]+kraw[i].nd.st);
}
if(p1<INF && p2<INF) ans=min(ans, p1+p2+kraw[i].nd.nd);
}
rep(i, m) if(wazne[i]) {
V[kraw[i].st.nd].pb(i);
swap(kraw[i].st.st, kraw[i].st.nd);
dijkstra(0, 0, 0);
dijkstra(n-1, 1, 0);
if(odl[n-1][0]<INF && odl[0][1]<INF) {
ans=min(ans, odl[n-1][0]+odl[0][1]+kraw[i].nd.nd);
}
swap(kraw[i].st.st, kraw[i].st.nd);
V[kraw[i].st.nd].pop_back();
}
cout << (ans==INF?-1:ans) << '\n';
}
