#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 1;
const long long mod = 1e9 + 7;
const int MaxN = 2e2 + 5;
const int MaxM = 5e4 + 5;
struct Edge
{
int u, v;
long long c, d;
};
int n, m;
Edge edges[MaxM];
vector<int> graph[MaxN];
vector<int> revgraph[MaxN];
void Inp()
{
cin >> n >> m;
for (int x = 1; x <= m; x++)
{
cin >> edges[x].u >> edges[x].v >> edges[x].c >> edges[x].d;
graph[edges[x].u].push_back(x);
revgraph[edges[x].v].push_back(x);
}
}
long long Dis[2][MaxN][MaxN];
bool visited[MaxN];
long long curDis[MaxN];
void Dijkstra(int id, int s, int k)
{
for (int x = 1; x <= n; x++)
{
visited[x] = false;
Dis[id][x][k] = inf;
curDis[x] = inf;
}
visited[k] = true;
Dis[id][s][k] = 0;
curDis[s] = 0;
while (true)
{
pair<long long, int> p = make_pair(inf, 0);
for (int x = 1; x <= n; x++)
{
if (!visited[x] && curDis[x] < inf)
{
p = min(p, make_pair(curDis[x], x));
}
}
if (p.second == 0)
{
break;
}
int u = p.second;
visited[u] = true;
Dis[id][u][k] = curDis[u];
for (int id : graph[u])
{
int v = edges[id].v;
long long w = edges[id].c;
if (!visited[v])
{
curDis[v] = min(curDis[v], curDis[u] + w);
}
}
curDis[u] = inf;
}
}
long long revDis[2][MaxN][MaxN];
void RevDijkstra(int id, int s, int k)
{
for (int x = 1; x <= n; x++)
{
visited[x] = false;
revDis[id][x][k] = inf;
curDis[x] = inf;
}
visited[k] = true;
revDis[id][s][k] = 0;
curDis[s] = 0;
while (true)
{
pair<long long, int> p = make_pair(inf, 0);
for (int x = 1; x <= n; x++)
{
if (!visited[x] && curDis[x] < inf)
{
p = min(p, make_pair(curDis[x], x));
}
}
if (p.second == 0)
{
break;
}
int u = p.second;
visited[u] = true;
revDis[id][u][k] = curDis[u];
for (int id : revgraph[u])
{
int v = edges[id].u;
long long w = edges[id].c;
if (!visited[v])
{
curDis[v] = min(curDis[v], curDis[u] + w);
}
}
curDis[u] = inf;
}
}
long long best[2][MaxN];
long long revbest[2][MaxN];
long long secbest[2][MaxN];
long long revsecbest[2][MaxN];
int posbest[2][MaxN];
int revposbest[2][MaxN];
void Exc()
{
Dijkstra(0, 1, 0);
Dijkstra(1, n, 0);
for (int x = 1; x <= n; x++)
{
Dis[0][x][1] = inf;
Dis[1][x][n] = inf;
}
Dis[0][1][1] = Dis[1][n][n] = 0;
for (int x = 2; x <= n; x++)
{
Dijkstra(0, 1, x);
}
for (int x = 1; x < n; x++)
{
Dijkstra(1, n, x);
}
RevDijkstra(0, 1, 0);
RevDijkstra(1, n, 0);
for (int x = 1; x <= n; x++)
{
revDis[1][x][n] = inf;
revDis[0][x][1] = inf;
}
for (int x = 2; x <= n; x++)
{
RevDijkstra(0, 1, x);
}
for (int x = 1; x < n; x++)
{
RevDijkstra(1, n, x);
}
long long res = min(Dis[0][n][0] + Dis[1][1][0], inf);
for (int id = 0; id < 2; id++)
{
for (int x = 1; x <= n; x++)
{
best[id][x] = secbest[id][x] = inf;
posbest[id][x] = 0;
if (id == 0 && x == 1)
{
best[id][x] = 0;
continue;
}
if (id == 1 && x == n)
{
best[id][x] = 0;
continue;
}
for (int y : revgraph[x])
{
int u = edges[y].u;
long long w = edges[y].c;
if (best[id][x] > Dis[id][u][x] + w)
{
secbest[id][x] = best[id][x];
best[id][x] = Dis[id][u][x] + w;
posbest[id][x] = y;
}
else if (secbest[id][x] > Dis[id][u][x] + w)
{
secbest[id][x] = Dis[id][u][x] + w;
}
}
}
}
for (int id = 0; id < 2; id++)
{
for (int x = 1; x <= n; x++)
{
revbest[id][x] = revsecbest[id][x] = inf;
revposbest[id][x] = 0;
if (id == 0 && x == 1)
{
revbest[id][x] = 0;
continue;
}
if (id == 1 && x == n)
{
revbest[id][x] = 0;
continue;
}
for (int y : graph[x])
{
int u = edges[y].v;
long long w = edges[y].c;
if (revbest[id][x] > revDis[id][u][x] + w)
{
revsecbest[id][x] = revbest[id][x];
revbest[id][x] = revDis[id][u][x] + w;
revposbest[id][x] = y;
}
else if (revsecbest[id][x] > revDis[id][u][x] + w)
{
revsecbest[id][x] = revDis[id][u][x] + w;
}
}
}
}
for (int x = 1; x <= m; x++)
{
int u = edges[x].u, v = edges[x].v;
long long w = edges[x].c;
long long cur = edges[x].d;
long long p1 = w, p11 = revDis[1][v][0];
if (posbest[0][v] == x)
{
p1 += secbest[0][v];
p11 += secbest[0][v];
}
else
{
p1 += best[0][v];
p11 += best[0][v];
}
if (revposbest[1][u] == x)
{
p1 += revsecbest[1][u];
}
else
{
p1 += revbest[1][u];
}
cur += min(p1, min(Dis[0][n][v], p11));
p1 = w;
p11 = revDis[0][v][0];
if (posbest[1][v] == x)
{
p1 += secbest[1][v];
p11 += secbest[1][v];
}
else
{
p1 += best[1][v];
p11 += best[1][v];
}
if (revposbest[0][u] == x)
{
p1 += revsecbest[0][u];
}
else
{
p1 += revbest[0][u];
}
//if (x == 4) cout << revbest[0][u] << " ";
cur += min(p1, min(Dis[1][1][v], p11));
res = min(res, cur);
}
if (res >= inf)
{
cout << -1;
}
else
{
cout << res;
}
}
int main()
{
//freopen("C.INP", "r", stdin);
//freopen("C.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
