#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;
vector<int>V[207];
pair<pair<int,int>,pair<int,int>>kraw[LIM];
int odl[207][5], wazne[LIM], n, m;
void dijkstra(int v, int odw, int f, int z) {
rep(i, n) odl[i][f]=odl[i][4]=INF;
priority_queue<pair<int,pair<int,int>>>q;
q.push({0, {v, -1}});
odl[v][4]=0;
while(!q.empty()) {
int o=-q.top().st, p=q.top().nd.st, lst=q.top().nd.nd; q.pop();
if(odl[p][f]<=o) continue;
odl[p][f]=o;
if(z) wazne[lst]=1;
for(auto i : V[p]) {
if(!odw) {
if(kraw[i].st.st==p && o+kraw[i].nd.st<odl[kraw[i].st.nd][f]) {
if(o+kraw[i].nd.st<odl[kraw[i].st.nd][4]) {
odl[kraw[i].st.nd][4]=o+kraw[i].nd.st;
q.push({-o-kraw[i].nd.st, {kraw[i].st.nd, i}});
}
}
} else {
if(kraw[i].st.nd==p && o+kraw[i].nd.st<odl[kraw[i].st.st][f]) {
if(o+kraw[i].nd.st<odl[kraw[i].st.st][4]) {
odl[kraw[i].st.st][4]=o+kraw[i].nd.st;
q.push({-o-kraw[i].nd.st, {kraw[i].st.st, i}});
}
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
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);
V[kraw[i].st.nd].pb(i);
}
rep(i, n) random_shuffle(all(V[i]));
dijkstra(0, 0, 0, 1);
dijkstra(n-1, 1, 1, 1);
dijkstra(n-1, 0, 2, 1);
dijkstra(0, 1, 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]) {
swap(kraw[i].st.st, kraw[i].st.nd);
dijkstra(0, 0, 0, 0);
dijkstra(n-1, 0, 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);
}
cout << (ans==INF?-1:ans) << '\n';
}
