#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
short skip_cin = 0;
const long long INF = 1e17, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);
struct edge
{
long long to, w, idx;
};
long long n;
vector<edge> g[200], rg[200];
void dijkstra(long long s, vector<long long>& dist, vector<pair<long long, long long>>& p, bool rev, long long del = -1)
{
if (rev)
{
swap(g, rg);
}
dist[s] = 0;
vector<bool> used(n);
while (true)
{
long long v = -1;
for (long long i = 0; i < n; i++)
{
if (!used[i] && dist[i] != INF && (v == -1 || dist[i] < dist[v]))
{
v = i;
}
}
if (v == -1)
{
break;
}
used[v] = true;
for (auto& i : g[v])
{
if (i.idx == del)
{
continue;
}
if (dist[v] + i.w < dist[i.to])
{
dist[i.to] = dist[v] + i.w;
p[i.to] = { v, i.idx };
}
}
}
if (rev)
{
swap(g, rg);
}
}
vector<long long> get_path(long long a, long long b, vector<pair<long long, long long>>& p)
{
if (p[b].first == -1)
{
return {};
}
vector<long long> res;
while (b != a)
{
res.push_back(p[b].second);
b = p[b].first;
}
return res;
}
void solve()
{
long long m;
cin >> n >> m;
vector<long long> rv(m), w(m);
vector<pair<long long, long long>> frto(m);
for (long long i = 0; i < m; i++)
{
long long a, b, c, d;
cin >> a >> b >> c >> d;
a--; b--;
g[a].push_back({ b, c, i });
rg[b].push_back({ a, c, i });
rv[i] = d;
frto[i] = { a, b };
w[i] = c;
}
vector<long long> da(n, INF), db(n, INF), rda(n, INF), rdb(n, INF);
vector<pair<long long, long long>> pa(n, { -1, -1 }), pb(n, { -1, -1 }), TRASH(n);
dijkstra(0, da, pa, false);
dijkstra(n - 1, db, pb, false);
dijkstra(0, rda, TRASH, true);
dijkstra(n - 1, rdb, TRASH, true);
vector<long long> ea = get_path(0, n - 1, pa), eb = get_path(n - 1, 0, pb);
vector<bool> used(m);
for (auto& i : ea)
{
used[i] = true;
}
for (auto& i : eb)
{
used[i] = true;
}
long long ans = min(INF, da[n - 1] + db[0]);
for (long long i = 0; i < m; i++)
{
auto [x, y] = frto[i];
if (!used[i])
{
ans = min(ans, rv[i] + min(da[n - 1], da[y] + w[i] + rdb[x]) + min(db[0], db[y] + w[i] + rda[x]));
continue;
}
g[y].push_back({ x, w[i], INF });
vector<long long> fucka(n, INF), fuckb(n, INF);
dijkstra(0, fucka, TRASH, false, i);
dijkstra(n - 1, fuckb, TRASH, false, i);
ans = min(ans, fucka[n - 1] + fuckb[0] + rv[i]);
g[y].pop_back();
}
cout << (ans == INF ? -1 : ans) << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand(time(NULL));
int tst = 1;
//cin >> tst;
while (tst--)
{
solve();
}
return 0;
}
/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/
