#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
using pii = pair<int, int>;
const int N = 202;
const int INF = 2e9 + 9;
struct edge {
int from, to, c, d;
};
int n, m;
int pe[N], pv[N];
vector<int> g[N];
vector<int> dijkstra(int src, vector<edge>& e) {
vector<int> dist(n + 1, INF);
dist[src] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [c, v] = pq.top();
pq.pop();
if (c != dist[v]) {
continue;
}
for (int i : g[v]) {
int u = v ^ e[i].from ^ e[i].to;
if (c + e[i].c < dist[u]) {
pe[u] = i;
pv[u] = v;
dist[u] = c + e[i].c;
pq.push({dist[u], u});
}
}
}
return dist;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
vector<edge> e(m);
for (int i = 0; i < m; ++i) {
int u, v, c, d;
cin >> u >> v >> c >> d;
e[i] = {u, v, c, d};
g[u].push_back(i);
}
vector<bool> marked(m);
vector<vector<int>> dist(n + 1);
dist[1] = dijkstra(1, e);
if (dist[1][n] != INF) {
int x = n;
while (x != 1) {
assert(pv[x] != 0);
marked[pe[x]] = true;
x = pv[x];
}
}
for (int i = 1; i <= n; ++i) {
pe[i] = pv[i] = 0;
}
dist[n] = dijkstra(n, e);
if (dist[n][1] != INF) {
int x = 1;
while (x != n) {
assert(pv[x] != 0);
marked[pe[x]] = true;
x = pv[x];
}
}
int ans = INF;
if (dist[1][n] != INF && dist[n][1] != INF) {
ans = dist[1][n] + dist[n][1];
}
for (int i = 2; i < n; ++i) {
dist[i] = dijkstra(i, e);
}
for (int i = 0; i < m; ++i) {
if (marked[i]) {
continue;
}
int u = e[i].from, v = e[i].to;
if (dist[1][n] != INF && dist[n][v] != INF && dist[u][1] != INF) {
ans = min(ans, e[i].d + dist[1][n] + dist[n][v] + e[i].c + dist[u][1]);
}
if (dist[1][v] != INF && dist[u][n] != INF && dist[n][1] != INF) {
ans = min(ans, e[i].d + dist[1][v] + e[i].c + dist[u][n] + dist[n][1]);
}
if (dist[1][v] != INF && dist[u][n] != INF && dist[n][v] != INF && dist[u][1] != INF) {
ans = min(ans, e[i].d + dist[1][v] + e[i].c + dist[u][n] + dist[n][v] + e[i].c + dist[u][1]);
}
}
for (int i = 0; i < m; ++i) {
if (!marked[i]) {
continue;
}
int u = e[i].from, v = e[i].to;
g[u].erase(find(g[u].begin(), g[u].end(), i));
g[v].push_back(i);
swap(e[i].from, e[i].to);//useless, but for the logic
dist[1] = dijkstra(1, e);
dist[n] = dijkstra(n, e);
if (dist[1][n] != INF && dist[n][1] != INF) {
ans = min(ans, e[i].d + dist[1][n] + dist[n][1]);
}
g[v].pop_back();
g[u].push_back(i);
swap(e[i].from, e[i].to);
}
if (ans == INF) {
ans = -1;
}
cout << ans << '\n';
return 0;
}
