#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 200 + 10;
const int maxm = 5e4 + 10;
const int inf = 1e9;
int n, m;
int a[maxm], b[maxm], c[maxm], d[maxm];
vector<pair<int,int> > g[maxn];
int dp[maxn], pd[maxn], cn[maxn], pr[maxn];
bool mark[maxn];
int dijkstra(int src, int snk){
memset(dp, 63, sizeof dp);
memset(mark, 0, sizeof mark);
memset(cn, 0, sizeof cn);
dp[src] = 0;
for (int i = 0; i < n; i++){
int v = -1;
for (int 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]){
int idx = e.second;
int u = e.first, w = c[idx];
if (dp[u] > dp[v] + w){
dp[u] = dp[v] + w;
pr[u] = idx;
cn[u] = 1;
}
else if (dp[u] == dp[v] + w)
cn[u] ++;
}
}
return dp[snk];
}
int reshpa(int src, int snk){
for (int i = 0; i < m; i++)
g[b[i]].push_back({a[i], i});
for (int i = 1; i <= n; i++)
pd[i] = dp[i];
int ret = dijkstra(snk, src);
for (int i = 1; i <= n; i++){
swap(dp[i], pd[i]);
g[i].clear();
}
return ret;
}
int shpa(int src, int snk){
for (int i = 0; i < m; i++)
g[a[i]].push_back({b[i], i});
int ret = dijkstra(src, snk);
for (int i = 1; i <= n; i++)
g[i].clear();
return ret;
}
bool visited[maxm];
ll ans[maxm];
void solve(int src, int snk){
reshpa(src, snk);
int now = shpa(src, snk);
memset(visited, 0, sizeof visited);
if (now <= inf){
vector<int> sp;
int 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]);
}
}
shpa(src, snk);
for (int 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 (int 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 (int 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;
}
