#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
struct cmp {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
return a.first > b.first;
}
};
const int N = 200, M = 50000;
vector<int> graph[2][N];
int deg[N], rev_deg[N], path[N], dist[N], _from[M], _to[M], weight[M], cost[M];
int dist_w[4][M][N], dist_i[4][N];
int n, m;
int from(int g, int id) {
return g == 0 ? _from[id] : _to[id];
}
int to(int g, int id) {
return g == 0 ? _to[id] : _from[id];
}
void dijkstra(int start, int g, bool flag, int del = -1) {
fill(dist, dist + n, INT_MAX);
if (flag) fill(path, path + n, -1);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
q.emplace(0, start);
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (dist[u] > d) {
continue;
}
for (int e : graph[g][u]) {
if (e != del && dist[u] + weight[e] < dist[to(g, e)]) {
dist[to(g, e)] = dist[u] + weight[e];
if (flag) path[to(g, e)] = e;
q.emplace(dist[to(g, e)], to(g, e));
}
}
}
}
void _solve(int g, int start, int it) {
dijkstra(start, g, true);
memcpy(dist_i[it], dist, sizeof dist);
for (int i = 0; i < n; i++) {
if (path[i] != -1) {
dijkstra(start, g, false, path[i]);
memcpy(dist_w[it][path[i]], dist, sizeof dist);
}
}
}
int Get(int it, int id, int u) {
return dist_w[it][id][u] == -1 ? dist_i[it][u] : dist_w[it][id][u];
}
void solve() {
cin >> n >> m;
memset(dist_w, -1, sizeof dist_w);
for (int i = 0; i < m; i++) {
cin >> _from[i] >> _to[i] >> weight[i] >> cost[i];
_from[i]--, _to[i]--;
deg[_from[i]]++, rev_deg[_to[i]]++;
}
for (int i = 0; i < n; i++) {
graph[0][i].reserve(deg[i]);
graph[1][i].reserve(rev_deg[i]);
}
for (int i = 0; i < m; i++) {
graph[0][_from[i]].push_back(i);
graph[1][_to[i]].push_back(i);
}
_solve(0, 0, 0);
_solve(0, n - 1, 1);
_solve(1, 0, 2);
_solve(1, n - 1, 3);
int ans = INT_MAX;
if (dist_i[0][n - 1] != INT_MAX && dist_i[1][0] != INT_MAX) {
ans = dist_i[0][n - 1] + dist_i[1][0];
}
for (int u = 0; u < n; u++) {
for (int id : graph[0][u]) {
int AB = INT_MAX, BA = INT_MAX;
AB = min(AB, Get(0, id, n - 1));
if (Get(0, id, to(0, id)) != INT_MAX && Get(3, id, from(0, id)) != INT_MAX) {
AB = min(AB, Get(0, id, to(0, id)) + Get(3, id, from(0, id)) + weight[id]);
}
BA = min(BA, Get(1, id, 0));
if (Get(1, id, to(0, id)) != INT_MAX && Get(2, id, from(0, id)) != INT_MAX) {
BA = min(BA, Get(1, id, to(0, id)) + Get(2, id, from(0, id)) + weight[id]);
}
if (AB == INT_MAX || BA == INT_MAX) {
continue;
}
ans = min(ans, AB + BA + cost[id]);
}
}
cout << (ans == INT_MAX ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
