#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a, b, c, d;
};
ll n, m;
ll M = 210, inf = 1e18;
vector<vector<ll>> g(M), gt(M);
vector<Edge> e;
vector<vector<ll>> dijkstra(ll s) {
vector<vector<ll>> dist(M, vector<ll>(2, inf));
dist[s][0] = 0;
priority_queue<pair<ll, pair<ll, ll>>> pq;
pq.push({0, {s, 0}});
while(pq.size()) {
auto[dv, stat] = pq.top(); pq.pop();
auto[v, msk] = stat; dv *= -1;
if(dist[v][msk]!=dv) continue;
for(auto i : g[v]) {
if(dist[e[i].b][msk] > dist[v][msk] + e[i].c) {
dist[e[i].b][msk] = dist[v][msk] + e[i].c;
pq.push({-dist[e[i].b][msk], {e[i].b, msk}});
}
}
if(msk) continue;
for(auto i : gt[v]) {
if(dv + e[i].c + e[i].d < dist[e[i].a][1]) {
dist[e[i].a][1] = dv + e[i].c + e[i].d;
pq.push({-dist[e[i].a][1], {e[i].a, 1}});
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(ll i=0; i<m; ++i) {
Edge x;
cin >> x.a >> x.b >> x.c >> x.d;
g[x.a].push_back(i);
gt[x.b].push_back(i);
e.emplace_back(x);ll
}
vector<vector<ll>> dist1 = dijkstra(1);
vector<vector<ll>> distn = dijkstra(n);
ll ans = dist1[n][0] + distn[1][0];
ans = min(ans, dist1[n][1] + distn[1][0]);
ans = min(ans, dist1[n][0] + distn[1][1]);
if(ans >= inf) cout << "-1\n";
else cout << ans << "\n";
return 0;
}
