#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int MAXN=207, MAXM=5e4+7, INF=2e9+7;
vector<int>V[MAXN];
pair<pair<int,int>,pair<int,int>>T[MAXM];
int odl[MAXN][4], odw[MAXM], n, m;
void dijkstra1(int v, int r, int p) {
rep(i, n) odl[i][p]=INF;
priority_queue<pair<int,pair<int,int>>>q;
q.push({0, {v, -1}});
while(!q.empty()) {
int o=-q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
if(odl[a][p]<=o) continue;
odl[a][p]=o;
if(!r) odw[b]=1;
for(auto i : V[a]) {
if(!r) {
if(T[i].st.st==a && odl[T[i].st.nd][p]==INF) {
q.push({-o-T[i].nd.st, {T[i].st.nd, i}});
}
} else {
if(T[i].st.nd==a && odl[T[i].st.st][p]==INF) {
q.push({-o-T[i].nd.st, {T[i].st.st, i}});
}
}
}
}
}
void dijkstra2(int v) {
rep(i, n) odl[i][0]=INF;
priority_queue<pair<int,int>>q;
q.push({0, v});
while(!q.empty()) {
int o=-q.top().st, a=q.top().nd; q.pop();
if(odl[a][0]<=o) continue;
odl[a][0]=o;
for(auto i : V[a]) if(odl[T[i].st.nd][0]==INF) q.push({-o-T[i].nd.st, T[i].st.nd});
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, m) {
cin >> T[i].st.st >> T[i].st.nd >> T[i].nd.st >> T[i].nd.nd;
--T[i].st.st;
--T[i].st.nd;
V[T[i].st.st].pb(i);
V[T[i].st.nd].pb(i);
}
dijkstra1(0, 0, 0);
dijkstra1(0, 1, 1);
dijkstra1(n-1, 0, 2);
dijkstra1(n-1, 1, 3);
int ans=INF;
if(odl[n-1][0]<INF && odl[0][2]<INF) ans=odl[n-1][0]+odl[0][2];
rep(i, m) if(!odw[i]) {
int a=odl[n-1][0], b=odl[0][2];
if(odl[T[i].st.nd][0]<INF && odl[T[i].st.st][3]<INF) {
a=min(a, odl[T[i].st.nd][0]+odl[T[i].st.st][3]+T[i].nd.st);
}
if(odl[T[i].st.nd][2]<INF && odl[T[i].st.st][1]<INF) {
b=min(b, odl[T[i].st.nd][2]+odl[T[i].st.st][1]+T[i].nd.st);
}
ans=min(ans, a+b+T[i].nd.nd);
}
rep(i, m) if(odw[i]) {
swap(T[i].st.st, T[i].st.nd);
dijkstra2(0);
if(odl[n-1][0]<INF) {
int akt=odl[n-1][0];
dijkstra2(n-1);
if(odl[0][0]<INF) {
akt+=odl[0][0];
ans=min(ans, akt+T[i].nd.nd);
}
}
swap(T[i].st.st, T[i].st.nd);
}
cout << (ans==INF?-1:ans) << '\n';
}
