#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int mod = 1e16 + 7;
const int N = 205;
int n, m;
vector<multiset<int>> g(N);
vector<vector<multiset<int>>> c(N, vector<multiset<int>>(N));
int dijkstra(int i, int j)
{
vi dist(n + 1, mod);
dist[i] = 0;
queue<int> q;
q.push(i);
while (!q.empty())
{
int v = q.front();
q.pop();
for (auto ch : g[v])
{
int x = *c[v][ch].begin();
if (dist[ch] > dist[v] + x)
{
dist[ch] = dist[v] + x;
q.push(ch);
}
}
}
return dist[j];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<vi> roads(m);
for (int i = 0; i < m; i++)
{
int x, y, a, b;
cin >> x >> y >> a >> b;
roads[i].pb(x);
roads[i].pb(y);
roads[i].pb(a);
roads[i].pb(b);
g[x].insert(y);
c[x][y].insert(a);
}
int ans = dijkstra(1, n) + dijkstra(n, 1);
for (auto p : roads)
{
int x = p[0], y = p[1], a = p[2], b = p[3];
g[x].erase(g[x].find(y));
g[y].insert(x);
c[x][y].erase(c[x][y].find(a));
c[y][x].insert(a);
ans = min(ans, dijkstra(1, n) + dijkstra(n, 1) + b);
g[y].erase(g[y].find(x));
g[x].insert(y);
c[y][x].erase(c[y][x].find(a));
c[x][y].insert(a);
}
cout << (ans >= mod ? -1 : ans) << '\n';
}
