#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200, M = 50000;
const ll infL = 3e18;
bool in_s[M], in_n[M], used[N];
ll distS[N], distN[N], distAllS[N], distAllN[N], tmp[N];
int A[M], B[M], W[M], D[M], P[M], revP[M], n, m;
vector<pair<int, int>> newg[N];
void dijkstra(int s, vector<pair<int, int>> g[], ll dist[], bool need, bool in[], int blocked = -1) {
fill(dist, dist + n, infL);
dist[s] = 0;
set<pair<ll, int>> st;
st.insert({0, s});
while (!st.empty()) {
auto [ww, x] = *st.begin();
st.erase(st.begin());
for (auto [to, i]: g[x]) {
if (i != blocked && dist[to] > dist[x] + W[i]) {
st.erase({dist[to], to});
dist[to] = dist[x] + W[i];
st.insert({dist[to], to});
}
}
}
if (need) {
for (int i = 0; i < n; ++i) {
newg[i].clear();
}
for (int i = 0; i < n; ++i) {
for (auto [to, j]: g[i]) {
if (dist[to] == dist[i] + W[j]) {
newg[i].emplace_back(to, j);
}
}
}
memset(used, 0, sizeof(used[0]) * n);
function<void(int)> dfs = [&](int v) {
used[v] = true;
for (auto [to, i]: newg[v]) {
if (!used[to]) {
in[i] = true;
dfs(to);
}
}
};
dfs(s);
}
}
vector<pair<int, int>> g[N], revg[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> A[i] >> B[i] >> W[i] >> D[i];
--A[i], --B[i];
P[i] = (int) g[A[i]].size();
revP[i] = (int) revg[B[i]].size();
g[A[i]].emplace_back(B[i], i);
revg[B[i]].emplace_back(A[i], i);
}
dijkstra(0, g, distS, true, in_s);
dijkstra(0, revg, distAllS, false, used);
dijkstra(n - 1, g, distN, true, in_n);
dijkstra(n - 1, revg, distAllN, false, used);
ll ans = infL;
ans = min(ans, distS[n - 1] + distN[0]);
for (int i = 0; i < m; ++i) {
ll valSN, valNS;
if (in_s[i]) {
dijkstra(0, g, tmp, false, in_s, i);
valSN = tmp[n - 1];
} else {
valSN = min(distS[n - 1], distS[B[i]] + W[i] + distAllN[A[i]]);
}
if (in_n[i]) {
dijkstra(n - 1, g, tmp, false, in_n, i);
valNS = tmp[0];
} else {
valNS = min(distN[0], distN[B[i]] + W[i] + distAllS[A[i]]);
}
ans = min(ans, D[i] + valNS + valSN);
}
cout << (ans == infL ? -1 : ans);
return 0;
}
