#include <bits/stdc++.h>
using namespace std;
#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif
using ll = long long;
const ll inf = 1'000'000'000'000'000'000;
#define int long long
struct edge{
int u;
int c;
int ind;
edge(int a, int b, int c1){
u = a;
c = b;
ind = c1;
}
};
int n;
vector<vector<edge>> v, v1;
vector<int> dij_ban(int start, int ban, vector<vector<edge>> &g){
vector<int> d(n, inf);
d[start] = 0;
vector<int> used(n);
while(true){
int u = -1;
for(int i = 0; i < n; i++){
if(!used[i] && ((u == -1) || d[i] < d[u])){
u = i;
}
}
if(u == -1){
break;
}
used[u] = 1;
int dd = d[u];
if(u == ban){
continue;
}
for(auto [i, j, ind] : g[u]){
if(dd + j < d[i]){
d[i] = dd + j;
}
}
}
d[ban] = inf;
return d;
}
void solve(){
int m;
cin >> n >> m;
n += 2;
v.resize(n);
v1.resize(n);
vector<array<int, 4>> z;
for(int i = 0; i < m; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
v[a].emplace_back(b, c, i);
v1[b].emplace_back(a, c, i);
z.push_back({a, b, c, d});
}
v[0].emplace_back(1, 0, m);
v[1].emplace_back(0, 0, m + 1);
v1[0].emplace_back(1, 0, m + 1);
v1[1].emplace_back(0, 0, m);
z.push_back({0, 1, 0, 0});
z.push_back({1, 0, 0, 0});
v[n - 1].emplace_back(n - 2, 0, m + 2);
v[n - 2].emplace_back(n - 1, 0, m + 3);
v1[n - 1].emplace_back(n - 2, 0, m + 3);
v1[n - 2].emplace_back(n - 1, 0, m + 2);
z.push_back({n - 1, n - 2, 0, 0});
z.push_back({n - 2, n - 1, 0, 0});
m += 4;
vector<vector<int>> dist(n, vector<int>(n, inf));
for(auto i : z){
dist[i[0]][i[1]] = min(dist[i[0]][i[1]], i[2]);
}
for(int i = 0; i < n; i++){
dist[i][i] = 0;
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector<vector<int>> without0(n), withoutn(n), without01(n), withoutn1(n);
for(int i = 0; i < n; i++){
without0[i] = dij_ban(0, i, v);
without01[i] = dij_ban(0, i, v1);
withoutn[i] = dij_ban(n - 1, i, v);
withoutn1[i] = dij_ban(n - 1, i, v1);
}
int ans = inf;
ans = min(ans, dist[0][n - 1] + dist[n - 1][0]);
vector<vector<int>> vans1(n), vans2(n);
vector<pair<int, int>> ANS1(n, {inf, inf}), ANS2(n, {inf, inf});
for(int b = 0; b < n; b++){
vans1[b].resize(v[b].size());
for(int ind = 0; ind < v[b].size(); ind++){
auto [i, j, ind1] = v[b][ind];
if(i == b){
continue;
}
vans1[b][ind] = j + withoutn1[b][i];
if(vans1[b][ind] < ANS1[b].first){
ANS1[b].second = ANS1[b].first;
ANS1[b].first = vans1[b][ind];
}else if(vans1[b][ind] < ANS1[b].second){
ANS1[b].second = vans1[b][ind];
}
}
vans2[b].resize(v[b].size());
for(int ind = 0; ind < v[b].size(); ind++){
auto [i, j, ind1] = v[b][ind];
if(i == b){
continue;
}
vans2[b][ind] = j + without01[b][i];
if(vans2[b][ind] < ANS2[b].first){
ANS2[b].second = ANS2[b].first;
ANS2[b].first = vans2[b][ind];
}else if(vans2[b][ind] < ANS2[b].second){
ANS2[b].second = vans2[b][ind];
}
}
}
vector<vector<int>> piske(n, vector<int>(m, -1));
for(int i = 0; i < n; i++){
for(int j = 0; j < v[i].size(); j++){
piske[i][v[i][j].ind] = j;
}
}
for(int ind = 0; ind < z.size(); ind++){
auto [b, a, c, dd] = z[ind];
if(a == b){
continue;
}
int cost = min(c, dist[a][b]);
int ans1 = inf;
// cout << "aaaaaaaa " << b << ' ' << a << ' ' << c << ' ' << dd << endl;
ans1 = min(ans1, without0[b][a] + cost + withoutn1[a][b]);
ans1 = min(ans1, without0[b][n - 1]);
ans1 = min(ans1, without0[a][n - 1]);
int popa = piske[b][ind];
int mn1 = inf;
if(vans1[b][popa] == ANS1[b].first){
mn1 = ANS1[b].second;
}else{
mn1 = ANS1[b].first;
}
ans1 = min(ans1, without0[a][b] + mn1);
int ans2 = inf;
ans2 = min(ans2, withoutn[b][a] + cost + without01[a][b]);
ans2 = min(ans2, withoutn[b][0]);
ans2 = min(ans2, withoutn[a][0]);
int mn2 = inf;
if(vans2[b][popa] == ANS2[b].first){
mn2 = ANS2[b].second;
}else{
mn2 = ANS2[b].first;
}
ans2 = min(ans2, withoutn[a][b] + mn2);
ans = min(ans, ans1 + ans2 + dd);
}
if(ans >= inf){
cout << -1 << endl;
return;
}
cout << ans << endl;
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
