#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
int n;
vector<vector<pair<int, int>>> v, v1;
vector<int> dij(int start, vector<vector<pair<int, int>>> &g){
vector<int> d(n, inf);
d[start] = 0;
set<pair<int, int>> q;
for(int i = 0; i < n; i++){
q.insert({d[i], i});
}
while(!q.empty()){
auto [dd, u] = *q.begin();
q.erase(q.begin());
for(auto [i, j] : g[u]){
if(dd + j < d[i]){
q.erase({d[i], i});
d[i] = dd + j;
q.insert({d[i], i});
}
}
}
return d;
}
vector<int> dij_ban(int start, int ban, vector<vector<pair<int, int>>> &g){
vector<int> d(n, inf);
d[start] = 0;
set<pair<int, int>> q;
for(int i = 0; i < n; i++){
q.insert({d[i], i});
}
while(!q.empty()){
auto [dd, u] = *q.begin();
q.erase(q.begin());
if(u == ban){
continue;
}
for(auto [i, j] : g[u]){
if(dd + j < d[i]){
q.erase({d[i], i});
d[i] = dd + j;
q.insert({d[i], i});
}
}
}
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);
v1[b].emplace_back(a, c);
z.push_back({a, b, c, d});
}
v[0].emplace_back(1, 0);
v[1].emplace_back(0, 0);
v1[0].emplace_back(1, 0);
v1[1].emplace_back(0, 0);
z.push_back({0, 1, 0, 0});
z.push_back({1, 0, 0, 0});
v[n - 1].emplace_back(n - 2, 0);
v[n - 2].emplace_back(n - 1, 0);
v1[n - 1].emplace_back(n - 2, 0);
v1[n - 2].emplace_back(n - 1, 0);
z.push_back({n - 2, n - 1, 0, 0});
z.push_back({n - 1, n - 2, 0, 0});
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 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);
}
// for(auto i : withoutn){
// for(auto j : i){
// cout << j << ' ';
// }
// cout << endl;
// }
// cout << endl;
int ans = inf;
ans = min(ans, dist[0][n - 1] + dist[n - 1][0]);
for(auto [b, a, c, dd] : z){
// cout << "aaaaaaaaaaaaaa\n";
// cout << b + 1 << ' ' << a + 1 << ' ' << c << ' ' << dd << endl;
int cost = min(c, dist[a][b]);
int ans1 = inf;
ans1 = min(ans1, without0[b][a] + cost + withoutn1[a][b]);
ans1 = min(ans1, without0[b][n - 1]);
ans1 = min(ans1, without0[a][n - 1]);
for(auto [i, j] : v[b]){
if(i == a){
continue;
}
ans1 = min(ans1, without0[a][b] + j + withoutn1[b][i]);
}
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]);
for(auto [i, j] : v[b]){
if(i == a){
continue;
}
ans2 = min(ans2, withoutn[a][b] + j + without01[b][i]);
// cout << "zzz " << i << ' ' << j << endl;
// cout << ans2 << endl;
}
// cout << ans2 << endl;
ans = min(ans, ans1 + ans2 + dd);
// cout << ans1 << ' ' << ans2 << ' ' << dd << endl;
// cout << ans << endl;
}
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();
}
}
