#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
using namespace std;
#define int long long
#define pi pair<int,int>
const int N = 203, M = 5 * 10^4 + 3;
const int inf = 1e17;
vector<vector<int>> dis(N, vector<int>(N, inf));
multiset<pi> g[N];
vector<int> wt;
vector<int> cost;
int n, m;
int dijkstra(int x, int y){
vector<int> dist(n + 1, inf);
vector<bool> vis(n + 1, 0);
priority_queue<pi, vector<pi>, greater<pi>> ms;
ms.push({0, x});
dist[x] = 0;
while (!ms.empty()) {
auto p = ms.top();
int v = p.second;
ms.pop();
if(vis[v])
continue;
vis[v] = true;
for (auto ch : g[v]){
int ch_v = ch.first;
int ch_wt = wt[ch.second];
if (dist[v] + ch_wt < dist[ch_v]){
dist[ch_v] = dist[v] + ch_wt;
ms.push({dist[ch_v], ch_v});
}
}
}
return dist[y];
}
signed main()
{
cin >> n >> m;
wt.resize(m);
cost.resize(m);
for (int i = 1; i <= n; i++)
{
dis[i][i] = 0;
}
pi edges[m];
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v >> wt[i] >> cost[i];
g[u].insert({v, i});
edges[i] = {u, v};
dis[u][v] = min(dis[u][v], wt[i]);
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
int ans = min(inf, dis[1][n] + dis[n][1]);
for (int i = 0; i < m; i++)
{
int u = edges[i].first, v = edges[i].second;
if (min(dis[1][n], dis[1][v] + wt[i] + dis[u][n]) +
min(dis[n][1], dis[n][v] + wt[i] + dis[u][1]) + cost[i] <
ans)
{
g[u].erase(g[u].find({v, i}));
g[v].insert({u, i});
ans = min(ans, cost[i] + dijkstra(1, n) + dijkstra(n, 1));
g[v].erase(g[v].find({edges[i].first, i}));
g[u].insert({v, i});
}
}
if (ans == inf)
{
cout << -1;
return (int)0;
}
cout << ans;
}
