#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>
#include <cmath>
typedef long long ll;
using namespace std;
struct edge {
ll v;
ll c;
ll d;
};
ll dfs(vector<vector<edge>> graf, ll n0, ll n1, ll n, edge block, ll blockstart) {
vector<bool> vis(n + 1, false);
edge e;
e.v = blockstart;
e.c = block.c;
e.d = block.d;
if(blockstart != 0) {
graf[block.v].push_back(e);
}
vector<ll> odl(n + 1, 1);
odl[n0] = 0;
priority_queue<pair<ll, ll>> q;
q.push({0, n0});
while(!q.empty()) {
ll v = q.top().second;
ll w = q.top().first;
q.pop();
vis[v] = true;
for(edge se : graf[v]) {
if(v == blockstart && se.v == block.v && se.c == block.c && se.d == block.d) continue;
if(!vis[se.v]) {
if(odl[se.v] < 0) {q.push({se.c, se.v});odl[se.v] = w + se.c;}
if(odl[se.v] > (se.c + w)) {
q.push({se.c, se.v});
odl[se.v] = se.c + w;
}
}
}
}
//cout << odl[n1] << '\n';
return odl[n1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, m; cin >> n >> m;
vector<vector<edge>> graf(n + 1);
vector<pair<ll, edge>> edgelist;
for(int i = 0; i < m; i++) {
ll u, v, c, d; cin >> u >> v >> c >> d;
edge e;
e.v = v;
e.c = -1 * c;
e.d = d;
graf[u].push_back(e);
edgelist.push_back({u, e});
}
ll d1 = -1 * dfs(graf, 1, n, n, edge(), 0);
ll d2 = -1 * dfs(graf, n, 1, n, edge(), 0);
ll mn = (d1 >= 0 && d2 >= 0 ? d1 + d2 : -1);
for(int i = 0; i < m; i++) {
ll v = edgelist[i].first;
edge e = edgelist[i].second;
ll d1 = -1 * dfs(graf, 1, n, n, e, v);
ll d2 = -1 * dfs(graf, n, 1, n, e, v);
//cout << d1 << " " << d2 << '\n';
if(d1 < 0 || d2 < 0) continue;
mn = min(mn, d1 + d2 + e.d);
}
cout << mn;
return 0;
}
