#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
const long mxN = 1e5 + 7, inf = 2e9 + 7;
int n, m, u[mxN], v[mxN], c[mxN], sw[mxN];
ll mn[mxN][5];
ii trace[mxN][5];
bool use[5][mxN];
vector<ii> w[mxN][2];
void DFS(int stt, int en, int spe, int id, int tt)
{
for (int i = 1; i <= n; i++)
{
mn[i][tt] = inf;
trace[i][tt] = {0, 0};
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, stt});
mn[stt][tt] = 0;
while (pq.size())
{
ii j = pq.top();
pq.pop();
if (j.fi != mn[j.se][tt])
continue;
for (ii i : w[j.se][id])
{
if (i.se != spe && mn[i.fi][tt] > j.fi + c[i.se])
{
mn[i.fi][tt] = j.fi + c[i.se];
trace[i.fi][tt] = {j.se, i.se};
pq.push({mn[i.fi][tt], i.fi});
}
}
}
while (en)
{
use[tt][trace[en][tt].se] = 1;
en = trace[en][tt].fi;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(a".INP", "r", stdin);
//freopen(a".OUT", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> u[i] >> v[i] >> c[i] >> sw[i];
w[u[i]][0].push_back({v[i], i});
w[v[i]][1].push_back({u[i], i});
}
DFS(1, n, 0, 0, 0);
DFS(n, 1, 0, 0, 1);
DFS(1, n, 0, 1, 2);
DFS(n, 1, 0, 1, 3);
ll ans = mn[n][0] + mn[1][1];
for (int i = 1; i <= m; i++)
{
ll l, r;
if (use[0][i])
{
w[v[i]][0].push_back({u[i], 0});
DFS(1, n, i, 0, 4);
w[v[i]][0].pop_back();
l = mn[n][4];
}
else
l = min(mn[n][0], mn[u[i]][3] + mn[v[i]][0] + c[i]);
if (use[1][i])
{
w[u[i]][1].push_back({v[i], 0});
DFS(n, 1, i, 0, 4);
w[u[i]][1].pop_back();
r = mn[1][4];
}
else
r = min(mn[1][1], mn[u[i]][2] + mn[v[i]][1] + c[i]);
ans = min(l + r + sw[i], ans);
}
if (ans >= inf)
cout << -1;
else
cout << ans;
}
