#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll maxn = 200 + 10;
const ll maxm = 5e4 + 10;
const ll inf = 1e9;
ll n, m;
ll a[maxm], b[maxm], c[maxm], d[maxm];
vector<pair<ll,ll> > g[maxn];
ll dp[maxn], pd[maxn], pr[maxn];
bool mark[maxn];
ll dijkstra(ll src, ll snk){
memset(dp, 63, sizeof dp);
memset(mark, 0, sizeof mark);
dp[src] = 0;
for (ll i = 0; i < n; i++){
ll v = -1;
for (ll j = 1; j <= n; j++)
if (!mark[j] and (v == -1 or dp[v] > dp[j]))
v = j;
if (v == -1)
break;
mark[v] = 1;
for (auto e : g[v]){
ll idx = e.second;
ll u = e.first, w = c[idx];
if (dp[u] > dp[v] + w){
dp[u] = dp[v] + w;
pr[u] = idx;
}
}
}
return dp[snk];
}
ll reshpa(ll src, ll snk){
for (ll i = 0; i < m; i++)
g[b[i]].push_back({a[i], i});
for (ll i = 1; i <= n; i++)
pd[i] = dp[i];
ll ret = dijkstra(snk, src);
for (ll i = 1; i <= n; i++){
swap(dp[i], pd[i]);
g[i].clear();
}
return ret;
}
ll shpa(ll src, ll snk){
for (ll i = 0; i < m; i++)
g[a[i]].push_back({b[i], i});
ll ret = dijkstra(src, snk);
for (ll i = 1; i <= n; i++)
g[i].clear();
return ret;
}
bool visited[maxm];
ll ans[maxm];
void solve(ll src, ll snk){
reshpa(src, snk);
ll now = shpa(src, snk);
memset(visited, 0, sizeof visited);
if (now <= inf){
vector<ll> sp;
ll tmp = snk;
while (tmp != src){
sp.push_back(pr[tmp]);
tmp = a[pr[tmp]];
}
for (auto it : sp){
swap(a[it], b[it]);
ans[it] += shpa(src, snk);
visited[it] = 1;
swap(a[it], b[it]);
}
}
for (ll i = 0; i < m; i++){
if (visited[i])
continue;
ll t = dp[b[i]], s = pd[a[i]];
ans[i] += min((ll)now, s + t + c[i]);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (ll i = 0; i < m; i++)
cin >> a[i] >> b[i] >> c[i] >> d[i];
ll answer = shpa(1, n) + shpa(n, 1);
solve(1, n);
solve(n, 1);
ll t = answer;
for (ll i = 0; i < m; i++){
answer = min(answer, ans[i] + d[i]);
t = min(t, ans[i]);
}
if (t >= inf)
return cout << -1 << endl, 0;
cout << answer << endl;
}
