#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)
const int maxn = 2e5 + 10, maxm = 2e2 + 10, oo = 1e18, lg = 19, sq = 1400, mod = 998244353;
int n, m, ln, ans;
struct edge{
int id;
int u;
int v;
int w;
int c;
} e[maxn];
set<pii> ed[maxm][maxm];
int d[maxm][maxm];
int par[maxm][maxm];
bool seen[maxm][maxm];
bool brg[2][maxn];
void djk(int r, bool f = 0)
{
for (int i = 1; i <= n;i++)
d[r][i] = oo;
for (int i = 1; i <= n;i++)
seen[r][i] = 0;
d[r][r] = 0;
for (int j = 1; j <= n;j++){
int v = 0;
for (int i = 1; i <= n;i++)
if(!seen[r][i] && (!v || d[r][v] > d[r][i]))
v = i;
seen[r][v] = 1;
for (int u = 1; u <= n;u++)
if(!seen[r][u] && (d[r][u] > (d[r][v] + (*ed[v][u].begin()).F))){
d[r][u] = min(d[r][u], d[r][v] + (*ed[v][u].begin()).F);
if(f)
par[r][u] = (*ed[v][u].begin()).S;
}
}
}
void mark(int t, int s){
int id = par[s][t];
if(!id || t == s)
return;
brg[s == n][id] = 1;
mark(e[id].u, s);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m;i++){
cin >> e[i].u >> e[i].v >> e[i].w >> e[i].c;
e[i].id = i;
ed[e[i].u][e[i].v].insert({e[i].w, i});
}
for (int i = 1; i <= n;i++)
for (int j = 1; j <= n;j++)
ed[i][j].insert({oo, 0});
for (int i = 1; i <= n; i++)
djk(i, 1);
mark(1, n);
mark(n, 1);
ans = d[1][n] + d[n][1];
for (int i = 1; i <= m;i++){
if(!(brg[0][i] || brg[1][i])){
// e[i].u -> e[i].v
// e[i].v -> e[i].u
int go = min(d[1][n], d[1][e[i].v] + e[i].w + d[e[i].u][n]);
int come = min(d[n][1], d[n][e[i].v] + e[i].w + d[e[i].u][1]);
ans = min(ans, e[i].c + go + come);
}
}
for (int i = 1; i <= m;i++)
if(brg[0][i] || brg[1][i]){
ed[e[i].u][e[i].v].erase({e[i].w, i});
swap(e[i].u, e[i].v);
ed[e[i].u][e[i].v].insert({e[i].w, i});
djk(1);
djk(n);
ans = min(ans, d[1][n] + d[n][1] + e[i].c);
ed[e[i].u][e[i].v].erase({e[i].w, i});
swap(e[i].u, e[i].v);
ed[e[i].u][e[i].v].insert({e[i].w, i});
}
cout << (ans >= oo? -1 : ans);
}
signed main()
{
threesum;
int t = 1;
//cin >> t;
while(t--)
solve();
}
