#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = INT_MAX;
const int LNF = 1e18;
const int MOD = 1000000007;
const double eps = 1e-12;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
const int MAX = 210;
int n, m;
int dis[MAX][MAX];
int dis2[MAX][MAX];
int res;
void FloydWarshall(){
FOR(k, 1, n, 1){
FOR(i, 1, n, 1){
FOR(j, 1, n, 1){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
// 1 -> n, n -> 1
vector<pii> eout, ein;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
FOR(i, 1, n, 1){
FOR(j, 1, n, 1){
dis[i][j] = dis2[i][j] = LNF;
}
}
FOR(i, 1, m, 1){
int u, v, c, d;
cin>>u>>v>>c>>d;
dis[u][v] = min(dis[u][v], c);
dis2[v][u] = min(dis2[v][u], c+d);
if(u == 1 and v == n) eout.eb(c, c+d);
if(u == n and v == 1) ein.eb(c, c+d);
}
FloydWarshall();
// not inverting an edge
int res = dis[1][n] + dis[n][1];
cerr<<"not inverting : "<<res<<endl;
// len. of cycle >= 3 :
// 1 ~> u -> n -> 1
// 1 -> u ~> n -> 1
// 1 -> u -> n ~> 1
int owo = LNF;
FOR(u, 2, n-1, 1){
res = min({res,
dis2[1][u] + dis[u][n] + dis[n][1],
dis[1][u] + dis2[u][n] + dis[n][1],
dis[1][u] + dis[u][n] + dis2[n][1],
dis2[u][1] + dis[n][u] + dis[1][n],
dis[u][1] + dis2[n][u] + dis[1][n],
dis[u][1] + dis[n][u] + dis2[1][n]
});
owo = min({owo,
dis2[1][u] + dis[u][n] + dis[n][1],
dis[1][u] + dis2[u][n] + dis[n][1],
dis[1][u] + dis[u][n] + dis2[n][1],
dis2[u][1] + dis[n][u] + dis[1][n],
dis[u][1] + dis2[n][u] + dis[1][n],
dis[u][1] + dis[n][u] + dis2[1][n]
});
}
cerr<<"len = 3 : "<<owo<<endl;
// len. of cycle == 2 : special case
// 1 -> n -> 1
res = min(res, dis[1][n] + dis[n][1]);
owo = dis[1][n] + dis[n][1];
// 1 -> n ~> 1
multiset<int> st;
for(pii e : eout) st.insert(e.F);
for(pii e : eout){
st.erase(st.find(e.F));
if(!st.empty()){
res = min(res, e.S + *st.begin());
owo = min(owo, e.S + *st.begin());
}
st.insert(e.F);
}
// 1 ~> n -> 1
st.clear();
for(pii e : ein) st.insert(e.F);
for(pii e : ein){
st.erase(st.find(e.F));
if(!st.empty()){
res = min(res, e.S + *st.begin());
owo = min(owo, e.S + *st.begin());
}
st.insert(e.F);
}
cerr<<"len = 2 : "<<owo<<endl;
if(res < LNF) cout<<res<<'\n';
else cout<<-1<<'\n';
return 0;
}
