#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll unsigned long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFLL 0x003f3f3f3f3f3f3f
// change if necessary
#define MAXN 210
using namespace std;
int n, m;
vector<array<int, 3>> adj[MAXN];
vector<array<int, 3>> radj[MAXN];
ll ans = INFLL;
ll dist_1[MAXN];
ll rdist_1[MAXN];
ll dist_n[MAXN];
ll rdist_n[MAXN];
bool vis[MAXN];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
void solve(int rem) {
for (int i = 0; i < n; i++) {
dist_1[i] = INFLL;
dist_n[i] = INFLL;
rdist_1[i] = INFLL;
rdist_n[i] = INFLL;
}
memset(vis, 0, sizeof vis);
pq = {};
pq.push({0, 0});
int cnt = 0;
while (!pq.empty()) {
auto [d, e] = pq.top();
pq.pop();
if (vis[e]) continue;
vis[e] = true;
dist_1[e] = d;
cnt++;
if (cnt == n) break;
if (e == rem) continue;
for (auto [u, c, dd] : adj[e]) {
if (!vis[u] && d + c < dist_1[u]) {
pq.push({d + c, u});
dist_1[u] = d + c;
}
}
}
memset(vis, 0, sizeof vis);
pq = {};
pq.push({0, n - 1});
cnt = 0;
while (!pq.empty()) {
auto [d, e] = pq.top();
pq.pop();
if (vis[e]) continue;
vis[e] = true;
rdist_n[e] = d;
cnt++;
if (cnt == 0) break;
for (auto [u, c, dd] : radj[e]) {
if (!vis[u] && d + c < rdist_n[u] && u != rem) {
pq.push({d + c, u});
rdist_n[u] = d + c;
}
}
}
memset(vis, 0, sizeof vis);
pq = {};
pq.push({0, n - 1});
cnt = 0;
while (!pq.empty()) {
auto [d, e] = pq.top();
pq.pop();
if (vis[e]) continue;
vis[e] = true;
dist_n[e] = d;
cnt++;
if (cnt == n) break;
if (e == rem) continue;
for (auto [u, c, dd] : adj[e]) {
if (!vis[u] && d + c < dist_n[u]) {
pq.push({d + c, u});
dist_n[u] = d + c;
}
}
}
memset(vis, 0, sizeof vis);
pq = {};
pq.push({0, 0});
cnt = 0;
while (!pq.empty()) {
auto [d, e] = pq.top();
pq.pop();
if (vis[e]) continue;
vis[e] = true;
rdist_1[e] = d;
cnt++;
if (cnt == n) break;
for (auto [u, c, dd] : radj[e]) {
if (!vis[u] && d + c < rdist_1[u] && u != rem) {
pq.push({d + c, u});
rdist_1[u] = d + c;
}
}
}
ans = min(ans, dist_1[n - 1] + dist_n[0]);
if (rem == n || adj[rem].empty()) return;
// path without flipping
pair<ll, ll> max_to_n = {dist_1[n - 1], dist_1[n - 1]};
pair<ll, ll> max_to_1 = {dist_n[0], dist_n[0]};
pair<ll, ll> r_max_to_1 = {rdist_1[rem], rdist_1[rem]};
pair<ll, ll> r_max_to_n = {rdist_n[rem], rdist_n[rem]};
for (const auto &e : adj[rem]) {
ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];
if (to_n <= max_to_n.first) {
max_to_n.second = max_to_n.first;
max_to_n.first = to_n;
} else if (to_n < max_to_n.second) {
max_to_n.second = to_n;
}
if (to_1 <= max_to_1.first) {
max_to_1.second = max_to_1.first;
max_to_1.first = to_1;
} else if (to_1 < max_to_1.second) {
max_to_1.second = to_1;
}
// no flip best prev path
ll r_to_n = e[1] + rdist_n[e[0]];
ll r_to_1 = e[1] + rdist_1[e[0]];
if (r_to_n <= r_max_to_n.first) {
r_max_to_n.second = r_max_to_n.first;
r_max_to_n.first = r_to_n;
} else if (r_to_n < r_max_to_n.second) {
r_max_to_n.second = r_to_n;
}
if (r_to_1 <= r_max_to_1.first) {
r_max_to_1.second = r_max_to_1.first;
r_max_to_1.first = r_to_1;
} else if (r_to_1 < r_max_to_1.second) {
r_max_to_1.second = r_to_1;
}
}
// consider flipping this
for (const auto &e : adj[rem]) {
ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
ll r_to_n = e[1] + rdist_n[e[0]];
if (to_n == max_to_n.first) {
to_n = max_to_n.second;
} else {
to_n = max_to_n.first;
}
if (r_to_n == r_max_to_n.first) {
r_to_n = r_max_to_n.second;
} else {
r_to_n = r_max_to_n.first;
}
to_n = min(to_n, dist_1[e[0]] + e[1] + r_to_n);
ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];
ll r_to_1 = e[1] + rdist_1[e[0]];
if (to_1 == max_to_1.first) {
to_1 = max_to_1.second;
} else {
to_1 = max_to_1.first;
}
if (r_to_1 == r_max_to_1.first) {
r_to_1 = r_max_to_1.second;
} else {
r_to_1 = r_max_to_1.first;
}
to_1 = min(to_1, dist_n[e[0]] + e[1] + r_to_1);
ans = min(ans, to_n + to_1 + e[2]);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, c, d; cin >> u >> v >> c >> d;
u--; v--;
adj[u].push_back({v, c, d});
radj[v].push_back({u, c, d});
}
for (int i = 0; i <= n; i++) {
solve(i);
}
if (ans == INFLL) {
cout << "-1\n";
} else {
cout << ans << '\n';
}
return 0;
}
