#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 200 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;
int n, m;
struct item {
int v, c, d, id;
};
struct node {
int u, v, c, d;
} a[100005];
vector <item> adj[N], adj1[N];
pii edge[N][N];
int length[N];
bool check[100005], check1[100005];
int road1[100005], road2[100005];
int dist[N][N];
void dijk(int u, vector <pii> &trace, int cant) {
for (int i = 1; i <= n; i++) {
length[i] = inf;
trace[i] = make_pair(0, 0);
}
length[u] = 0;
priority_queue <pii, vector <pii>, greater <pii> > q;
q.push({0, u});
while(q.size()) {
auto [val, uu] = q.top();
q.pop();
if (val > length[uu]) continue;
for (auto it : adj[uu]) {
int v = it.v, c = it.c, d = it.d, id = it.id;
if (id == cant) continue;
if (length[v] > length[uu] + c) {
length[v] = length[uu] + c;
trace[v] = {uu, id};
q.push({length[v], v});
}
}
}
}
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) if (i != j) dist[i][j] = inf;
}
for (int i = 1; i <= m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
a[i] = {u, v, c, d};
adj[u].push_back({v, c, d, i});
dist[u][v] = min(dist[u][v], (ll)c);
}
floyd();
vector <pii> trace1(n + 1, make_pair(0, 0));
dijk(1, trace1, -1);
int minn = length[n];
dijk(n, trace1, -1);
int minn2 = length[1];
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c;
if (dist[1][u] + c + dist[v][n] == minn) {
dijk(1, trace1, i);
road1[i] = length[n];
} else road1[i] = minn;
}
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c;
if (dist[n][u] + c + dist[v][1] == minn2) {
dijk(n, trace1, i);
road2[i] = length[1];
} else road2[i] = minn2;
}
int ans = inf;
ans = min(ans, dist[1][n] + dist[n][1]);
for (int i = 1; i <= m; i++) ans = min(ans, road1[i] + road2[i]);
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v, c = a[i].c, d = a[i].d;
int val1 = dist[1][u] + c + dist[v][n];
int val2 = dist[n][u] + c + dist[v][1];
ans = min(ans, val1 + road2[i] + d);
ans = min(ans, road1[i] + val2 + d);
}
if (ans >= inf) cout << -1;
else cout << ans;
return 0;
}
