#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
using namespace std;
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long
template<typename T>
struct Dijkstra {
const T INF = 1e18;
int n;
vector<vector<T>> adj;
vector<T> dist;
vector<int> par, path;
Dijkstra(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
adj.assign(n, vector<T>(n + 1, INF));
}
void minimise_directional_edge(int u, int v, T wt) {
adj[u][v] = min(adj[u][v], wt);
}
void minimise_bidirectional_edge(int u, int v, T wt) {
minimise_directional_edge(u, v, wt);
minimise_directional_edge(v, u, wt);
}
void set_directional_edge(int u, int v, T wt) {
adj[u][v] = wt;
}
void set_bidirectional_edge(int u, int v, T wt) {
set_directional_edge(u, v, wt);
set_directional_edge(v, u, wt);
}
T get_edge(int u, int v) {
return adj[u][v];
}
void run(vector<int> src) {
vector<bool> vis(n, false);
dist.assign(n, INF);
par.assign(n, -1);
path.clear();
for (const auto &node : src)
dist[node] = 0;
while (true) {
pair<T, int> mn = make_pair(INF, -1);
for (int u = 0; u < n; u++) {
if (!vis[u])
mn = min(mn, make_pair(dist[u], u));
}
if (mn.first >= INF) break;
vis[mn.second] = true;
for (int v = 0; v < n; v++) {
if (adj[mn.second][v] >= INF) continue;
T new_dist = mn.first + adj[mn.second][v];
if (new_dist < dist[v]) {
dist[v] = new_dist;
par[v] = mn.second;
}
}
}
}
void construct_path(int dest) {
path.clear();
path.push_back(dest);
while (par[path.back()] > -1)
path.push_back(par[path.back()]);
reverse(path.begin(), path.end());
}
bool reachable(int node) {
return par[node] > -1;
}
};
const int MXN = 205, INF = 1e18;
vector<pair<int, int>> edges[MXN][MXN];
bool in_path[MXN][MXN];
void solve() {
int N, M;
cin >> N >> M;
Dijkstra<int> inp_g(N + 1), inp_g_rev(N + 1);
while (M--) {
int u, v, c, d;
cin >> u >> v >> c >> d;
inp_g.minimise_directional_edge(u, v, c);
inp_g_rev.minimise_directional_edge(v, u, c);
edges[u][v].emplace_back(c, d);
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
sort(all(edges[i][j]));
inp_g.run(vector<int>{N});
vector<int> dist_t = inp_g.dist;
inp_g.construct_path(1);
for (int i = 1; i < sz(inp_g.path); i++)
in_path[inp_g.path[i - 1]][inp_g.path[i]] = true;
inp_g.run(vector<int>{1});
vector<int> dist_s = inp_g.dist;
inp_g.construct_path(N);
for (int i = 1; i < sz(inp_g.path); i++)
in_path[inp_g.path[i - 1]][inp_g.path[i]] = true;
inp_g_rev.run(vector<int>{1});
vector<int> dist_s_rev = inp_g_rev.dist;
inp_g_rev.run(vector<int>{N});
vector<int> dist_t_rev = inp_g_rev.dist;
int ans = dist_s[N] + dist_t[1];
for (int u = 1; u <= N; u++) {
for (int v = 1; v <= N; v++) {
if (edges[u][v].empty()) continue;
if (in_path[u][v]) {
int inp_g_edge_uv = inp_g.get_edge(u, v);
int inp_g_edge_vu = inp_g.get_edge(v, u);
inp_g.set_directional_edge(u, v, sz(edges[u][v]) > 1 ? edges[u][v][1].first : INF);
inp_g.set_directional_edge(v, u, edges[u][v][0].first);
inp_g.run(vector<int>{1});
int cost = inp_g.dist[N];
inp_g.run(vector<int>{N});
cost += inp_g.dist[1];
ans = min(ans, cost + edges[u][v][0].second);
inp_g.set_directional_edge(u, v, inp_g_edge_uv);
inp_g.set_directional_edge(v, u, inp_g_edge_vu);
}
for (int k = 0 + (in_path[u][v]); k < sz(edges[u][v]); k++) {
int cost1 = edges[u][v][k].first + edges[u][v][k].second + dist_s_rev[u] + dist_t[v]; // T to S
int cost2 = edges[u][v][k].first + edges[u][v][k].second + dist_s[v] + dist_t_rev[u]; // S to T
ans = min({ans, cost1 + dist_s[N], cost2 + dist_t[1], cost1 + cost2 - edges[u][v][k].second});
}
}
}
cout << (ans >= INF ? -1 : ans);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int TC = 1;
// cin >> TC;
while (TC--) solve();
}
