#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 201, M = 50001;
ll n, m;
// first -> distance, second -> length
vector<pair<ll, ll>> dist[N][N];
vector<ll> edges_cnt[N][N];
vector<pair<ll, ll>> adj[N];
ll c[M], d[M];
pair<ll, ll> edges[M];
void insert_dist(ll i, ll j, ll d, ll l) {
dist[i][j].push_back({d, l});
sort(dist[i][j].begin(), dist[i][j].end());
while (dist[i][j].size() > 2) {
dist[i][j].pop_back();
}
}
ll get_dist(ll u, ll v) { return dist[u][v][0].first; }
ll get_rdist(ll a, ll b, ll i) {
// we can't use edge number i
pair<ll, ll> p = {a, b};
if (edges[i] != p) {
return dist[a][b][0].first;
}
ll ans = 1e15;
bool dup_exists = false;
for (auto &e : edges_cnt[a][b]) {
if (e == i) {
continue;
}
if (c[e] == c[i]) {
dup_exists = true;
}
ans = min(ans, c[e]);
}
for (ll i = 0; i < dist[a][b].size(); ++i) {
if (dist[a][b][i].second != 1) {
ans = min(ans, dist[a][b][i].first);
continue;
}
if (!dup_exists && dist[a][b][i].first == c[i]) {
continue;
}
ans = min(ans, dist[a][b][i].first);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (ll i = 1; i <= n; ++i) {
adj[i].clear();
}
for (ll i = 1; i <= n; ++i) {
for (ll j = 1; j <= n; ++j) {
insert_dist(i, j, 1e15, 0);
}
}
for (ll i = 1; i <= n; ++i) {
insert_dist(i, i, 0, 0);
}
for (ll i = 0, u, v; i < m; ++i) {
cin >> u >> v >> c[i] >> d[i];
adj[u].emplace_back(v, i);
edges[i] = {u, v};
edges_cnt[u][v].push_back(i);
insert_dist(u, v, c[i], 1);
}
for (ll a = 1; a <= n; ++a) {
for (ll b = 1; b <= n; ++b) {
for (ll c = 1; c <= n; ++c) {
insert_dist(a, c, dist[a][b][0].first + dist[b][c][0].first,
dist[a][b][0].second + dist[b][c][0].second);
}
}
}
set<ll> edges_to, edges_from;
if (get_dist(1, n) != (ll)1e15) {
for (ll node = 1; node != n;) {
for (auto &nb : adj[node]) {
if (c[nb.second] + get_dist(nb.first, n) == get_dist(node, n)) {
edges_to.insert(nb.second);
node = nb.first;
}
}
}
}
if (get_dist(n, 1) != (ll)1e15) {
for (ll node = n; node != 1;) {
for (auto &nb : adj[node]) {
if (c[nb.second] + get_dist(nb.first, 1) == get_dist(node, 1)) {
edges_from.insert(nb.second);
node = nb.first;
}
}
}
}
ll ans = min((ll)1e15, get_dist(1, n) + get_dist(n, 1));
for (ll i = 0; i < m; ++i) {
ll u = edges[i].first, v = edges[i].second;
ll _ans = d[i];
if (edges_to.count(i)) {
_ans += get_rdist(1, v, i) + c[i] + get_rdist(u, n, i);
} else {
_ans +=
min(get_dist(1, n), get_rdist(1, v, i) + c[i] + get_rdist(u, n, i));
}
if (edges_from.count(i)) {
_ans += get_rdist(n, v, i) + c[i] + get_rdist(u, 1, i);
} else {
_ans +=
min(get_dist(n, 1), get_rdist(n, v, i) + c[i] + get_rdist(u, 1, i));
}
ans = min(ans, _ans);
}
if (ans == (ll)1e15) {
ans = -1;
}
cout << ans << "\n";
}
