// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 2e9+1;
int n, m, ans = INF;
vector<array<int, 3>> g[2][200];
vector<array<int, 4>> edges;
inline int add(int x, int y, int z){
if(max(x, max(y, z)) == INF) return INF;
return x + y + z;
}
inline int add(int x, int y){
if(max(x, y) == INF) return INF;
return x + y;
}
void bellmanFord(int r, int s, vector<int> &d, int k){
d.assign(n, INF);
d[s] = 0;
if(r == s) return;
for(int _=0; _<n; ++_)
for(auto &i : edges)
if(i[0] != r && i[1] != r) d[i[!k]] = min(d[i[!k]], d[i[k]] + i[2]);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
edges.resize(m);
for(auto &i : edges){
for(int j=0; j<4; ++j) cin >> i[j];
--i[0], --i[1];
g[0][i[0]].push_back({i[1], i[2], i[3]});
g[1][i[1]].push_back({i[0], i[2], i[3]});
}
for(int u=0; u<n; ++u){
vector<int> d[2], e[2];
for(int i=0; i<2; ++i){
bellmanFord(u, i ? n-1 : 0, d[i], 0);
bellmanFord(u, i ? n-1 : 0, e[i], 1);
}
for(auto &[v, w, x] : g[1][u])
for(int j=0; j<2; ++j)
d[j][u] = min(d[j][u], add(w, d[j][v]));
array<int, 2> x[2], y[2];
for(int j=0; j<2; ++j) x[j] = y[j] = {INF, -1};
for(int i=0; i<(int)g[0][u].size(); ++i){
for(int j=0; j<2; ++j){
y[j] = min(y[j], {add(e[j][g[0][u][i][0]], g[0][u][i][1]), i});
if(x[j] > y[j]) swap(x[j], y[j]);
}
}
if(u == 0) x[0][0] = y[0][0] = 0;
if(u==n-1) x[1][0] = y[1][0] = 0;
for(int i=0; i<(int)g[0][u].size(); ++i){
auto &[v, w, t] = g[0][u][i];
array<int, 2> uE;
for(int j=0; j<2; ++j) uE[j] = x[j][1] == i ? y[j][0] : x[j][0];
int a = add(d[0][v], w, uE[1]);
int b = add(d[1][v], w, uE[0]);
ans = min(ans, add(a, t, min(e[0][n-1], add(d[1][u], uE[0]))));
ans = min(ans, add(b, t, min(e[1][0], add(uE[1], d[0][u]))));
ans = min(ans, add(a, b, t));
}
}
vector<int> d[2];
bellmanFord(-1, 0, d[0], 0);
bellmanFord(-1, n-1, d[1], 0);
ans = min(ans, add(d[0][n-1], d[1][0]));
cout << (ans == INF ? -1 : ans) nl;
}
