#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int maxn = 201;
const int INF = 1e18;
vector<pair<int,int>> g[maxn];
vector<int> c,d;
vector<pair<int,int>> r;
int nr[maxn][maxn];
int dp[maxn][maxn];
int rr[maxn][maxn];
vector<bool> ru;
void rec(int s,int t)
{
if(dp[s][t] == INF)
{
return ;
}
if(rr[s][t] == -1)
{
ru[nr[s][t]] = 1;
return ;
}
int rp = rr[s][t];
rec(s,rp);
rec(rp,t);
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m;
for(int i =0;i < n;++i)
{
for(int j = 0;j < n;++j)
{
nr[i][j] = -1;
}
}
for(int i =0;i < m;++i)
{
int u,v,e,f;
cin >> u >> v >> e >> f;
u--;
v--;
g[u].push_back({v,i});
c.push_back(e);
d.push_back(f);
r.push_back({u,v});
if(nr[u][v] == -1 || c[nr[u][v]] > e)
{
nr[u][v] = i;
}
}
// cout << 1;
for(int i =0;i < n;++i)
{
for(int j = 0;j < n;++j)
{
if(i == j)
{
dp[i][j] = 0;
}
else
dp[i][j] = (nr[i][j] == -1 ? INF : c[nr[i][j]]);
rr[i][j] = -1;
}
}
// cout << 1;
for(int k = 0;k < n;++k)
{
for(int i = 0;i < n;++i)
{
for(int j = 0;j < n;++j)
{
if(dp[i][j] > dp[i][k] + dp[k][j])
{
dp[i][j] = dp[i][k] + dp[k][j];
rr[i][j] = k;
}
}
}
}
// cout << 1;
ru.resize(r.size());
rec(0,n-1);
rec(n-1,0);
int64_t ans = dp[0][n-1] + dp[n-1][0];
// cout << ans << ' ';
for(int i = 0;i < m;++i)
{
if(!ru[i])
{
//cout << i << ' ';
ans = min(ans,d[i] + min(dp[0][r[i].second] + c[i] + dp[r[i].first][n-1],dp[0][n-1]) + min(dp[n-1][r[i].second] + c[i] + dp[r[i].first][0],dp[n-1][0]));
}
else
{
int64_t tres = d[i];
vector<vector<pair<int,int>>> g2(n);
for(int j = 0;j < m;++j)
{
if(j != i)
{
g2[r[j].first].push_back({r[j].second,c[j]});
}
else
{
g2[r[j].second].push_back({r[j].first,c[j]});
}
}
vector<int> vis(n);
vector<int> d(n,INF);
d[0] = 0;
while(true)
{
int pm = -1;
for(int k = 0;k < n;++k)
{
if(!vis[k] && (pm == -1 || d[pm] > d[k]))
{
pm = k;
}
}
if(pm == -1 || d[pm] == INF)
{
break;
}
vis[pm] = 1;
for(auto [u,dd] : g2[pm])
{
if(d[pm] + dd < d[u])
{
d[u] = d[pm] + dd;
}
}
}
tres += d[n-1];
vis.clear();
vis.resize(n);
d.clear();
d.resize(n);
for(int j = 0;j < n;++j)
{
d[j] = INF;
}
d[n-1] = 0;
while(true)
{
int pm = -1;
for(int k = 0;k < n;++k)
{
if(!vis[k] && (pm == -1 || d[pm] > d[k]))
{
pm = k;
}
}
if(pm == -1 || d[pm] == INF)
{
break;
}
vis[pm] = 1;
for(auto [u,dd] : g2[pm])
{
if(d[pm] + dd < d[u])
{
d[u] = d[pm] + dd;
}
}
}
tres += d[0];
ans = min(ans,tres);
}
}
cout << (ans >= INF ? -1 : ans);
return 0;
}
