#include <bits/stdc++.h>
using namespace std;
#define int unsigned int
const int inf = 1e9;
const int some_fixed_seed = 12321;
struct ura
{
int u,v,c,d;
};
int n,m;
vector<ura>e;
int d[205][205];
vector<pair<int,int>>g[205];
int getdist(int sursa,int destinatie)
{
vector<int>dist(n + 1);
for (int i = 1; i <= n; i++)
dist[i] = inf;
priority_queue<pair<int,int>>pq;
pq.push({0,sursa});
while (!pq.empty())
{
int nod = pq.top().second,cost = -pq.top().first;
pq.pop();
if (dist[nod] == inf)
{
dist[nod] = cost;
for (auto vecin : g[nod])
pq.push({-(cost + vecin.second),vecin.first});
}
}
return dist[destinatie];
}
int tryrev(int idx)
{
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 0; i < e.size(); i++)
{
if (i == idx)
g[e[i].v].push_back({e[i].u,e[i].c});
else
g[e[i].u].push_back({e[i].v,e[i].c});
}
return getdist(1,n) + getdist(n,1);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
d[i][j] = inf;
for (int i = 1; i <= m; i++)
{
ura aux;
cin >> aux.u >> aux.v >> aux.c >> aux.d;
e.push_back(aux);
d[aux.u][aux.v] = min(d[aux.u][aux.v],aux.c);
}
shuffle(e.begin(),e.end(),default_random_engine(some_fixed_seed));
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
int ans = d[1][n] + d[n][1];
for (int i = 0; i < e.size(); i++)
{
auto it = e[i];
int d1 = min(d[1][n],d[1][it.v] + d[it.u][n] + it.c);
int d2 = min(d[n][1],d[n][it.v] + d[it.u][1] + it.c);
int cur = d1 + d2 + it.d;
if (cur < ans)
ans = min(ans,it.d + tryrev(i));
}
if (ans >= inf)
cout << -1;
else
cout << ans;
return 0;
}
/**
hai sa zicem ca dau invert la muchia u->v
costul o sa fie >= cost_rev + min(dist(1,n),cost_edge + dist(1,v) + dist(u,n)) + min(dist(n,1),cost_edge + dist(n,v) + dist(u,1))
dau random shuffle la muchii si verific o muchie doar daca are acest cost < ans
teoretic as verifica log muchii, asa o sa verific ceva mai multe dar hopefully tot putine
**/
