#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];
vector<int> in[2][maxn];
int d[maxm][maxm];
bool seen[maxm][maxm];
bool dag[2][maxn];
bool brg[2][maxn];
void djk(int r){
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] = min(d[r][u], d[r][v] + (*ed[v][u].begin()).F);
}
}
void ok(){
//djk(0, 1);
//djk(1, n);
}
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);
for (int b = 0; b < 2; b++)
for (int i = 1; i <= m; i++)
{
int s = (b ? n : 1);
int t = (b ? 1 : n);
if ((d[s][e[i].u] + e[i].w + d[e[i].v][t]) == d[s][t])
{
in[b][e[i].v].push_back(i);
dag[b][i] = 1;
}
}
ans = d[1][n] + d[n][1];
for (int v = 1; v <= n; v++)
for (int b = 0; b < 2;b++)
if(in[b][v].size() == 1)
brg[b][in[b][v][0]] = 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();
}
/*
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
*/
