#include <iostream>
#include<set>
#include<map>
#include<vector>
#define int long long
#define inf 1e15
using namespace std;
multiset<vector<int>> g[205];
int path(int s, int e, int n) {
set<pair<int, int>> q;
vector<int> dist(n + 1, inf);
q.insert({ 0, s }), dist[s] = 0;
while (q.size()) {
pair<int, int> f = *q.begin();
q.erase(q.begin());
if (f.second == e) return f.first;
for (auto y : g[f.second]) {
int i = y[0], x = y[1];
if (dist[i] > (x + f.first)) {
if (dist[i] != inf) q.erase({ dist[i], i });
dist[i] = (x + f.first);
q.insert({ dist[i], i });
}
}
}
return inf;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
set<vector<int>> e;
for (int i = 0; i < m; ++i) {
int u, v, c, d; cin >> u >> v >> c >> d;
g[u].insert({ v, c, d });
e.insert({ u, v, c, d });
}
int ans = path(1, n, n) + path(n, 1, n);
for (auto x : e) {
g[x[0]].erase(g[x[0]].find({ x[1], x[2], x[3] }));
g[x[1]].insert({ x[0], x[2], x[3] });
int cur = path(1, n, n) + path(n, 1, n) + x[3];
ans = min(ans, cur);
g[x[0]].insert({ x[1], x[2], x[3] });
g[x[1]].erase(g[x[1]].find({ x[0], x[2], x[3] }));
}
cout << ((ans >= inf) ? -1 : ans) << endl;
}
