#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const ll linf = 1e18 + 1;
const int NMAX = 201;
vector <pll> vec[NMAX][NMAX];
map<pair<pii, pll>, bool> used;
bool comp1(pll a, pll b){
return a.f < b.f;
}
bool comp2(pll a, pll b){
return a.f + a.s < b.f + b.s;
}
bool comp3(pll a, pll b){
return 2 * a.f + a.s < 2 * b.f + b.s;
}
vector <pair<ll, pll> > g[NMAX][2];
ll d[NMAX][NMAX][4];
void dijk(int a, int b, int ind, int bb){
d[a][b][ind] = 0;
if(a == b) return;
set <pll> q;
q.insert({d[a][b][ind], a});
while(!q.empty()){
int v = q.begin()->s;
q.erase(q.begin());
for(auto x : g[v][bb]){
int to = x.f;
if(to == b) continue;
ll len = x.s.f;
if(d[to][b][ind] > d[v][b][ind] + len){
q.erase({d[to][b][ind], to});
d[to][b][ind] = d[v][b][ind] + len;
q.insert({d[to][b][ind], to});
}
}
}
}
int n;
ll get(int v, int ind){
ll x = d[n][v][0];
ll y = d[1][v][1];
ll mn1, mn2;
mn1 = d[v][v][3];
mn2 = d[v][v][0];
for(int i = 0; i < g[v][0].size(); i++){
if(i == ind) continue;
int xx = g[v][0][i].f;
ll len = g[v][0][i].s.f;
mn1 = min(mn1, d[xx][v][3] + len);
}
for(int i = 0; i < g[v][1].size(); i++){
int xx = g[v][1][i].f;
ll len = g[v][1][i].s.f;
mn2 = min(mn2, d[xx][v][0] + len);
}
if(ind != g[v][0].size()){
int xx = g[v][0][ind].f;
ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
mn2 = min(mn2, d[xx][v][0] + len);
}
x = min(x, mn1 + mn2);
mn1 = d[v][v][2];
mn2 = d[v][v][1];
for(int i = 0; i < g[v][0].size(); i++){
if(i == ind) continue;
int xx = g[v][0][i].f;
ll len = g[v][0][i].s.f;
mn1 = min(mn1, d[xx][v][2] + len);
}
for(int i = 0; i < g[v][1].size(); i++){
int xx = g[v][1][i].f;
ll len = g[v][1][i].s.f;
mn2 = min(mn2, d[xx][v][1] + len);
}
if(ind != g[v][0].size()){
int xx = g[v][0][ind].f;
ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
mn2 = min(mn2, d[xx][v][1] + len);
}
y = min(mn1 + mn2, y);
return x + y;
}
int main(){
//ios_base::sync_with_stdio(false); cin.tie(0);
int m; cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
ll c, d; cin >> u >> v >> c >> d;
vec[u][v].pb({c, d});
}
//cout << 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vec[i][j].empty()) continue;
sort(vec[i][j].begin(), vec[i][j].end(), comp1);
g[i][0].pb({j, vec[i][j][0]});
used[{{i, j}, vec[i][j][0]}] = true;
sort(vec[i][j].begin(), vec[i][j].end(), comp2);
if(!used[{{i, j},vec[i][j][0]}])
g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
sort(vec[i][j].begin(), vec[i][j].end(), comp3);
if(!used[{{i, j},vec[i][j][0]}])
g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
}
}
// cout << 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 0; k < 4; k++){
d[i][j][k] = linf;
}
}
}
for(int i = 1; i <= n; i++){
for(auto to : g[i][0]){
int x = to.f;
pll v = to.s;
g[x][1].pb({i, v});
}
}
//cout << 1;
for(int i = 1; i <= n; i++){
dijk(1, i, 0, 0);
dijk(n, i, 1, 0);
dijk(1, i, 2, 1);
dijk(n, i, 3, 1);
}
//cout << 1;
ll ans = linf;
for(int i = n; i >= 1; i--){
for(int j = 0; j <= g[i][0].size(); j++){
//cout << i << ' ' << g[i][0][j].f << ' ' << get(i, j) << "\n";
ans = min(ans, get(i, j));
}
}
if(ans == linf) cout << -1 << "\n";
else cout << ans;
return 0;
}
