#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
const int inf = (int)4e18;
const bool tc = false;
const int mxn = 201;
struct edge {
int u, v, c, d;
};
struct ae {
int to, w, id;
};
int n, m;
vector<edge> e;
vector<ae> g[mxn], rg[mxn];
void dijk(int s, vector<ae> adj[], vi &dist, vi &parE, vi &parV, int ban = -1) {
dist.assign(n, inf);
parE.assign(n, -1);
parV.assign(n, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto &x : adj[u]) {
if (x.id == ban) continue;
int v = x.to, w = x.w;
if (d + w < dist[v]) {
dist[v] = d + w;
parE[v] = x.id;
parV[v] = u;
pq.push({dist[v], v});
}
}
}
}
struct Tree {
vi dist, parE, parV;
vi tin, tout;
int timer = 0;
vector<int> ch[mxn];
vi childOfEdge;
vvi rep;
};
void dfs_tree(int u, Tree &T) {
T.tin[u] = T.timer++;
for (int v : T.ch[u]) dfs_tree(v, T);
T.tout[u] = T.timer - 1;
}
bool is_anc(Tree &T, int a, int b) {
return T.tin[a] <= T.tin[b] && T.tout[b] <= T.tout[a];
}
void build_tree(Tree &T, int s, vector<ae> adj[]) {
dijk(s, adj, T.dist, T.parE, T.parV);
T.tin.assign(n, -1);
T.tout.assign(n, -1);
T.childOfEdge.assign(m, -1);
for (int i = 0; i < n; i++) T.ch[i].clear();
for (int v = 0; v < n; v++) {
if (v == s) continue;
if (T.parV[v] != -1) {
T.ch[T.parV[v]].pb(v);
T.childOfEdge[T.parE[v]] = v;
}
}
T.timer = 0;
dfs_tree(s, T);
}
inline int add3(int a, int b, int c) {
if (a >= inf || b >= inf || c >= inf) return inf;
if (a > inf - b) return inf;
a += b;
if (a > inf - c) return inf;
a += c;
return a;
}
inline int add2(int a, int b) {
if (a >= inf || b >= inf) return inf;
if (a > inf - b) return inf;
return a + b;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
if (tc) cin >> t;
while (t--) {
cin >> n >> m;
e.assign(m, {});
for (int i = 0; i < n; i++) {
g[i].clear();
rg[i].clear();
}
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
u--, v--;
e[i] = {u, v, c, d};
g[u].pb({v, c, i});
rg[v].pb({u, c, i});
}
Tree T1, TN, TtoN, Tto1;
build_tree(T1, 0, g);
build_tree(TN, n - 1, g);
build_tree(TtoN, n - 1, rg);
build_tree(Tto1, 0, rg);
T1.rep.assign(m, vi());
TN.rep.assign(m, vi());
TtoN.rep.assign(m, vi());
Tto1.rep.assign(m, vi());
vi tmpd, tmpe, tmpv;
for (int id = 0; id < m; id++) {
if (T1.childOfEdge[id] != -1) {
dijk(0, g, tmpd, tmpe, tmpv, id);
T1.rep[id] = tmpd;
}
if (TN.childOfEdge[id] != -1) {
dijk(n - 1, g, tmpd, tmpe, tmpv, id);
TN.rep[id] = tmpd;
}
if (TtoN.childOfEdge[id] != -1) {
dijk(n - 1, rg, tmpd, tmpe, tmpv, id);
TtoN.rep[id] = tmpd;
}
if (Tto1.childOfEdge[id] != -1) {
dijk(0, rg, tmpd, tmpe, tmpv, id);
Tto1.rep[id] = tmpd;
}
}
auto get_from_tree = [&](Tree &T, int id, int v) -> int {
int child = T.childOfEdge[id];
if (child == -1) return T.dist[v];
if (!is_anc(T, child, v)) return T.dist[v];
return T.rep[id][v];
};
int ans = add2(T1.dist[n - 1], TN.dist[0]);
for (int i = 0; i < m; i++) {
int u = e[i].u;
int v = e[i].v;
int c = e[i].c;
int d = e[i].d;
int A = get_from_tree(T1, i, n - 1); // dist_{G-e}(1,n)
int B = get_from_tree(T1, i, v); // dist_{G-e}(1,v)
int C = get_from_tree(TtoN, i, u); // dist_{G-e}(u,n)
int D = get_from_tree(TN, i, 0); // dist_{G-e}(n,1)
int E = get_from_tree(TN, i, v); // dist_{G-e}(n,v)
int F = get_from_tree(Tto1, i, u); // dist_{G-e}(u,1)
int go = min(A, add3(B, c, C));
int back = min(D, add3(E, c, F));
int cur = add3(go, back, d);
ans = min(ans, cur);
}
cout << (ans >= inf ? -1 : ans) << '\n';
}
}
