#include <iostream>
#include <vector>
#include <set>
using namespace std;
const long long INF = 1'000'000'000'000LL;
const int maxN = 200;
struct edge
{
int i;
int v;
long long fare;
long long modify_cost;
};
bool operator < (edge E, edge F)
{
return E.i < F.i;
};
multiset<edge> E[1+maxN];
vector< vector<long long> > dist(1+maxN, vector<long long>(1+maxN, INF));
vector<long long> dist1(1+maxN, INF);
vector<int> prevNode(1+maxN, -1);
vector<edge> prevEdge(1+maxN);
struct pos
{
int i;
};
bool operator < (pos X, pos Y)
{
if(dist1[X.i] == dist1[Y.i]) return X.i < Y.i;
return dist1[X.i] < dist1[Y.i];
}
vector<long long> distN(1+maxN, INF);
vector<int> prevNodeN(1+maxN, -1);
vector<edge> prevEdgeN(1+maxN);
struct posN
{
int i;
};
bool operator < (posN X, posN Y)
{
if(distN[X.i] == distN[Y.i]) return X.i < Y.i;
return distN[X.i] < distN[Y.i];
}
int main()
{
int N, M;
cin >> N >> M;
for(int i = 1; i <= N; i++) dist[i][i] = 0;
for(int e = 1; e <= M; e++)
{
int U, V, C, D;
cin >> U >> V >> C >> D;
E[U].insert(edge{e, V, C, D});
dist[U][V] = min(dist[U][V], (long long)C);
}
long long ans = INF;
//Part 1: Don't reverse anything
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
ans = min(ans, dist[1][N] + dist[N][1]);
//Part 2: Compute dijkstra tree
dist1[1] = 0;
set<pos> tbv;
for(int i = 1; i <= N; i++) tbv.insert(pos{i});
while(!tbv.empty())
{
int u = tbv.begin()->i;
tbv.erase(tbv.begin());
for(edge e:E[u])
{
int v = e.v;
long long w = e.fare;
if(dist1[u] + w < dist1[v])
{
tbv.erase(pos{v});
dist1[v] = dist1[u] + w;
prevNode[v] = u;
prevEdge[v] = e;
tbv.insert(pos{v});
}
}
}
// cerr << "ans = " << ans << '\n';
distN[N] = 0;
set<posN> tbvN;
for(int i = 1; i <= N; i++) tbvN.insert(posN{i});
while(!tbvN.empty())
{
int u = tbvN.begin()->i;
tbvN.erase(tbvN.begin());
for(edge e:E[u])
{
int v = e.v;
long long w = e.fare;
if(distN[u] + w < distN[v])
{
tbvN.erase(posN{v});
distN[v] = distN[u] + w;
prevNodeN[v] = u;
prevEdgeN[v] = e;
tbvN.insert(posN{v});
}
}
}
// cerr << "check\n";
// cerr << prevNode[N] << '\n';
for(int u = 1; u <= N; u++)
{
// cerr << "\n\n\n";
// cerr << "u = " << u << '\n';
multiset<edge> E1 = E[u];
for(edge e: E1)
{
// cerr << "e = " << e.i << ' ' << e.v << ' ' << e.fare << ' ' << e.modify_cost << '\n';
// cerr << "v = " << e.v << '\n';
int v = e.v;
bool flag1 = 0, flag2 = 0;
if(prevEdge[v].i != e.i)
{
ans = min(ans, dist[1][N] + dist[N][v] + e.fare + e.modify_cost + dist[u][1]);
flag1 = 1;
}
if(prevEdgeN[v].i != e.i)
{
ans = min(ans, dist[1][v] + e.fare + e.modify_cost + dist[u][N] + dist[N][1]);
flag2 = 1;
}
if(!flag1 || !flag2)
{
E[u].erase(E[u].find(e));
E[v].insert(edge{M+1, u, e.fare, e.modify_cost});
dist1[1] = 0;
for(int i = 2; i <= N; i++) dist1[i] = INF;
for(int i = 1; i <= N; i++) tbv.insert(pos{i});
while(!tbv.empty())
{
int u = tbv.begin()->i;
tbv.erase(tbv.begin());
for(edge e:E[u])
{
int v = e.v;
long long w = e.fare;
if(dist1[u] + w < dist1[v])
{
tbv.erase(pos{v});
dist1[v] = dist1[u] + w;
tbv.insert(pos{v});
}
}
}
distN[N] = 0;
for(int i = 1; i < N; i++) distN[i] = INF;
for(int i = 1; i <= N; i++) tbvN.insert(posN{i});
while(!tbvN.empty())
{
int u = tbvN.begin()->i;
tbvN.erase(tbvN.begin());
for(edge e:E[u])
{
int v = e.v;
long long w = e.fare;
if(distN[u] + w < distN[v])
{
tbvN.erase(posN{v});
distN[v] = distN[u] + w;
tbvN.insert(posN{v});
}
}
}
E[v].erase(E[v].find(edge{M+1, u, e.fare, e.modify_cost}));
E[u].insert(e);
ans = min(ans, dist1[N] + distN[1] + e.modify_cost);
}
// cerr << "e = " << e.i << ", ans = " << ans << '\n';
}
}
if(ans >= INF) ans = -1;
cout << ans << '\n';
}
