/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 210, maxm = 50010;
const ll inf = 1e17;
struct edge
{
int v, u;
ll c, d;
} e[maxm];
int n, m, used[maxn], cap[maxn][maxn];
ll dp[maxn][maxn], path[maxn][maxn], id[maxn][maxn];
ll dist[maxn], fr[maxn], sp[maxm];
void dijkstra(int v)
{
for (int i = 1; i <= n; i ++)
dist[i] = inf, used[i] = 0, fr[i] = -1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (i != j)
path[i][j] = inf;
}
for (int j = 1; j <= m; j ++)
{
if (e[j].c < path[e[j].v][e[j].u])
{
path[e[j].v][e[j].u] = e[j].c;
id[e[j].v][e[j].u] = j;
}
///path[e[j].v][e[j].u] = min(path[e[j].v][e[j].u], e[j].c);
}
int cur = v;
dist[cur] = 0;
while(true)
{
int mx = -1;
for (int i = 1; i <= n; i ++)
{
if (!used[i] && (mx == -1 || dist[i] < dist[mx]))
mx = i;
}
if (mx == -1)
break;
cur = mx;
used[cur] = 1;
for (int i = 1; i <= n; i ++)
{
if (!used[i] && dist[cur] + path[cur][i] < dist[i])
{
dist[i] = dist[cur] + path[cur][i];
fr[i] = id[cur][i];
}
}
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (i != j)
dp[i][j] = inf;
}
bool czero = true;
for (int i = 1; i <= m; i ++)
{
cin >> e[i].v >> e[i].u >> e[i].c >> e[i].d;
dp[e[i].v][e[i].u] = min(dp[e[i].v][e[i].u], (ll)e[i].c);
}
/**if (m <= 1000)
{
ll ans = 0;
dijkstra(1);
ans += dist[n];
dijkstra(n);
ans += dist[1];
for (int i = 1; i <= m; i ++)
{
swap(e[i].v, e[i].u);
ll cur = e[i].d;
dijkstra(1);
cur += dist[n];
///cout << dist[n] << endl;
dijkstra(n);
cur += dist[1];
///cout << dist[1] << endl;
ans = min(ans, cur);
///cout << i << " " << cur << endl;
swap(e[i].v, e[i].u);
}
if (ans <= inf)
cout << ans << endl;
else
cout << -1 << endl;
return;
}*/
ll ans = 0;
dijkstra(1);
ans += dist[n];
if (fr[n] != -1)
{
int st = n;
while(fr[st] != -1)
{
sp[fr[st]] = 1;
st = e[fr[st]].v;
}
}
dijkstra(n);
ans += dist[1];
if (fr[1] != -1)
{
int st = 1;
while(fr[st] != -1)
{
sp[fr[st]] = 1;
st = e[fr[st]].v;
}
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (dp[i][k] + dp[k][j] < dp[i][j])
dp[i][j] = dp[i][k] + dp[k][j];
}
for (int i = 1; i <= m; i ++)
{
if (sp[i])
{
swap(e[i].v, e[i].u);
ll cur = e[i].d;
dijkstra(1);
cur += dist[n];
///cout << dist[n] << endl;
dijkstra(n);
cur += dist[1];
///cout << dist[1] << endl;
ans = min(ans, cur);
///cout << i << " " << cur << endl;
swap(e[i].v, e[i].u);
continue;
}
int v = e[i].v, u = e[i].u;
ll cur = min(dp[1][u] + dp[v][n] + e[i].c, dp[1][n]) + min(dp[n][u] + dp[v][1] + e[i].c, dp[n][1]) + e[i].d;
///if (e[i].d < 74779 && e[i].c < 74779 && dp[v][1] < 74779)
///cout << cur << " " << e[i].d << " " << e[i].c << " " << dp[n][u] << " " << dp[v][1] << endl;
if (cur < ans)
ans = cur;
}
if (ans < inf)
cout << ans << endl;
else
cout << -1 << endl;
}
int main()
{
///freopen("test.txt", "r", stdin);
solve();
return 0;
}
/**
4 4
2 1 0 4
3 1 0 1
3 4 0 2
1 4 0 1
*/
