#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 256;
const int M = 50010;
vector<pii> A[N], T[N];
const int inf = 1.5e9+1000;
int w[M], p[M];
int dis0[N], disn[N], dis0T[N], disnT[N], disdard[N];
pii par[N];
pii edge[M];
bool is_path[M];
int n, m;
void dij(int s, int dis[], vector<pii> A[])
{
fill(dis, dis+n, inf);
fill(par, par+n, pii{-1, -1});
dis[s] = 0;
set<pii> st = {{0, s}};
while (st.size()) {
auto [d, v] = *st.begin();
st.erase(st.begin());
for (auto [u, e] : A[v]) {
int w = ::w[e];
if (d + w < dis[u]) {
st.erase({dis[u], u});
dis[u] = d+w;
par[u] = {v, e};
st.insert({dis[u], u});
}
}
}
}
#define int ll
void input()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (e,0,m) {
int v, u;
cin >> v >> u >> w[e] >> p[e];
--v; --u;
A[v].push_back({u,e});
T[u].push_back({v,e});
edge[e] = {v, u};
}
}
signed main()
{
input();
int ans = 0;
dij(0, dis0, A);
dij(0, dis0T, T);
ans += dis0[n-1];
int v = n-1;
for (;;) {
auto [u, e] = par[v];
if (u == -1)
break;
is_path[e] = 1;
v = u;
}
dij(n-1, disn, A);
dij(n-1, disnT, T);
ans += disn[0];
v = 0;
for (;;) {
auto [u, e] = par[v];
if (u == -1)
break;
is_path[e] = 1;
v = u;
}
Loop (e,0,m) {
auto [v, u] = edge[e];
if (is_path[e]) {
signed tmp = inf;
swap(tmp, w[e]);
w[m] = tmp;
A[u].push_back({v,m});
int x = p[e];
dij(0, disdard, A);
x += disdard[n-1];
dij(n-1, disdard, A);
x += disdard[0];
ans = min(ans, x);
A[u].pop_back();
w[e] = tmp;
} else {
int x = (int)dis0[u] + (int)w[e] + (int)disnT[v] + (int)disn[0];
int y = (int)dis0[n-1] + (int)disn[u] + (int)w[e] + (int)dis0T[v];
int z = (int)dis0[u] + (int)w[e] + (int)disnT[v]
+ (int)disn[u] + (int)w[e] + (int)dis0T[v];
ans = min(ans, p[e] + min({x, y, z}));
}
}
cout << (ans >= inf? -1: ans) << '\n';
}
