#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, pair<int, int> > > adj[205], rev[205];
int dist[205][205], d[205], final[205];
map<pair<int, int>, int> ans1, ans2;
set<pair<int, int> > edges1, edges2;
pair<int, int> pre[205][205];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i=1; i<=m; i++)
{
int u, v, c, d;
cin >> u >> v >> c >> d;
adj[u].push_back({v, {c, d}});
rev[v].push_back({u, {c, d}});
}
for (int i=1; i<=n; i++)
dist[1][i]=1e18;
dist[1][1]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>dist[1][j])
{
mn=dist[1][j];
u=j;
}
}
final[u]=1;
for (int j=0; j<adj[u].size(); j++)
{
int v=adj[u][j].first, w=adj[u][j].second.first;
if (dist[1][v]>dist[1][u]+w)
{
dist[1][v]=dist[1][u]+w;
pre[1][v]={u, j};
}
}
}
for (int i=1; i<=n; i++)
dist[i][1]=1e18, final[i]=0;
dist[1][1]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>dist[j][1])
{
mn=dist[j][1];
u=j;
}
}
final[u]=1;
for (int j=0; j<rev[u].size(); j++)
{
int v=rev[u][j].first, w=rev[u][j].second.first;
if (dist[v][1]>dist[u][1]+w)
{
dist[v][1]=dist[u][1]+w;
pre[v][1]={u, j};
}
}
}
for (int i=1; i<=n; i++)
dist[n][i]=1e18, final[i]=0;
dist[n][n]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>dist[n][j])
{
mn=dist[n][j];
u=j;
}
}
final[u]=1;
for (int j=0; j<adj[u].size(); j++)
{
int v=adj[u][j].first, w=adj[u][j].second.first;
if (dist[n][v]>dist[n][u]+w)
{
dist[n][v]=dist[n][u]+w;
pre[n][v]={u, j};
}
}
}
for (int i=1; i<=n; i++)
dist[i][n]=1e18, final[i]=0;
dist[n][n]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>dist[j][n])
{
mn=dist[j][n];
u=j;
}
}
final[u]=1;
for (int j=0; j<rev[u].size(); j++)
{
int v=rev[u][j].first, w=rev[u][j].second.first;
if (dist[v][n]>dist[u][n]+w)
{
dist[v][n]=dist[u][n]+w;
pre[v][n]={u, j};
}
}
}
if (dist[1][n]<1e14)
{
int cur=n;
while (cur!=1)
{
edges1.insert(pre[1][cur]);
cur=pre[1][cur].first;
}
}
if (dist[n][1]<1e14)
{
int cur=1;
while (cur!=n)
{
edges2.insert(pre[n][cur]);
cur=pre[n][cur].first;
}
}
for (auto edge:edges1)
{
for (int i=1; i<=n; i++)
d[i]=1e18, final[i]=0;
d[1]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>d[j])
{
mn=d[j];
u=j;
}
}
final[u]=1;
for (int j=0; j<adj[u].size(); j++)
{
int v=adj[u][j].first, w=adj[u][j].second.first;
if (edge!=make_pair(u, j))
d[v]=min(d[v], d[u]+w);
}
if (u==adj[edge.first][edge.second].first)
{
int v=edge.first, w=adj[edge.first][edge.second].second.first;
d[v]=min(d[v], d[u]+w);
}
}
ans1[edge]=d[n];
}
for (auto edge:edges2)
{
for (int i=1; i<=n; i++)
d[i]=1e18, final[i]=0;
d[n]=0;
for (int i=1; i<=n; i++)
{
int u, mn=1e18+1;
for (int j=1; j<=n; j++)
{
if (!final[j] && mn>d[j])
{
mn=d[j];
u=j;
}
}
final[u]=1;
for (int j=0; j<adj[u].size(); j++)
{
int v=adj[u][j].first, w=adj[u][j].second.first;
if (edge!=make_pair(u, j))
d[v]=min(d[v], d[u]+w);
}
if (u==adj[edge.first][edge.second].first)
{
int v=edge.first, w=adj[edge.first][edge.second].second.first;
d[v]=min(d[v], d[u]+w);
}
}
ans2[edge]=d[1];
}
int ans=dist[1][n]+dist[n][1];
for (int u=1; u<=n; u++)
{
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second.first, x=adj[u][i].second.second;
if (edges1.find({u, i})==edges1.end())
ans1[{u, i}]=min(dist[1][n], dist[1][v]+dist[u][n]+w);
if (edges2.find({u, i})==edges2.end())
ans2[{u, i}]=min(dist[n][1], dist[n][v]+dist[u][1]+w);
ans=min(ans, ans1[{u, i}]+ans2[{u, i}]+x);
}
}
cout << (ans>1e14?-1:ans);
}
