#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 210;
const int MAX_E = 50100;
const int INF = 1e9;
using Edge = pair<int, pair<int, int>>;
using Graph = vector<vector<Edge>>;
Graph g, rg, ue;
vector<int> d1, d2, rd1, rd2;
int n, m, u, v, w, r;
int used[MAX_E];
int last[MAX_N];
vector<pair<pair<int, int>, pair<int, int>>> edges;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int blk = -1;
void dijkstra(int start, Graph &g, vector<int> &dist) {
dist.resize(n + 1);
fill(dist.begin(), dist.end(), INF);
dist[start] = 0;
pq.emplace(0, start);
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
int curr = top.second;
int curr_dist = top.first;
if (dist[curr] < curr_dist) continue;
if (curr != start && blk == -1) used[last[curr]] = 1;
for (const auto &edge : g[curr]) {
int next = edge.first;
int new_dist = curr_dist + edge.second.first;
if (new_dist >= dist[next]) continue;
if (edge.second.second == blk) continue;
dist[next] = new_dist;
last[next] = edge.second.second;
pq.emplace(new_dist, next);
}
}
}
signed main() {
cin >> n >> m;
g.resize(n + 1);
rg.resize(n + 1);
ue.resize(n + 1);
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w >> r;
g[u].emplace_back(v, make_pair(w, i));
rg[v].emplace_back(u, make_pair(w, i));
edges.emplace_back(make_pair(u, v), make_pair(w, r));
}
dijkstra(1, g, d1);
dijkstra(n, g, d2);
dijkstra(1, rg, rd1);
dijkstra(n, rg, rd2);
int ans = d1[n] + d2[1];
for (int i = 0; i < m; ++i) if (used[i]) {
ue[edges[i].first.first].emplace_back(edges[i].first.second, make_pair(edges[i].second.first, i));
}
for (int i = 0; i < m; ++i) {
if (used[i]) continue;
int a = edges[i].first.first;
int b = edges[i].first.second;
int weight = edges[i].second.first;
int forward = min(d1[n], d1[b] + weight + rd2[a]);
int backward = min(d2[1], d2[b] + weight + rd1[a]);
int total_weight = edges[i].second.second + forward + backward;
ans = min(ans, total_weight);
}
for (int i = 0; i < m; ++i) {
if (!used[i]) continue;
int a = edges[i].first.first;
int b = edges[i].first.second;
int weight = edges[i].second.first;
blk = i;
vector<int> temp1, temp2;
g[b].emplace_back(a, make_pair(weight, -INF));
dijkstra(1, g, temp1);
dijkstra(n, g, temp2);
int total_weight = edges[i].second.second + temp1[n] + temp2[1];
ans = min(ans, total_weight);
g[b].pop_back();
}
cout << (ans >= INF ? -1 : ans);
return 0;
}
