#include "bits/stdc++.h"
#include <functional>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 200;
const int MAXM = 50000;
const ll INF = 1000'000'000'000'000ll;
int n, m;
struct edge {
int fr, to;
ll wcost;
ll scost;
bool crit;
};
edge E[MAXM + 5];
// vector<int> v[MAXN + 5], v2[MAXN + 5];
vector<vector<int>> adj;
vector<vector<int>> adj2;
int get_edge(int a, int b, int swapEg) {
int ret = -1;
if (swapEg != -1 && E[swapEg].fr == b && E[swapEg].to == a) {
ret = swapEg;
}
if (adj[a][b] != -1 && adj[a][b] != swapEg) {
if (ret == -1 || E[adj[a][b]].wcost < E[ret].wcost) {
ret = adj[a][b];
}
}
if (adj2[a][b] != -1 && adj2[a][b] != swapEg) {
if (ret == -1 || E[adj2[a][b]].wcost < E[ret].wcost) {
ret = adj2[a][b];
}
}
return ret;
}
void dijk(int source, vector<ll>& dist) {
dist.assign(n + 5, INF);
vector<bool> vis(n + 5, false);
typedef pair<ll, int> pli;
priority_queue<pli, vector<pli>, greater<pli>> Q;
dist[source] = 0;
vector<int> arrEdge(n + 5, 0);
for (int k = 1; k <= n; k++) {
int a = -1;
ll min = INF;
for (int i = 1; i <= n; i++) {
if (!vis[i] && dist[i] < min) {
a = i;
min = dist[i];
}
}
if (a == -1) break;
vis[a] = true;
for (int b = 1; b <= n; b++) {
int eg = get_edge(a, b, -1);
if (eg == -1) continue;
if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
dist[b] = dist[a] + E[eg].wcost;
arrEdge[b] = eg;
}
}
}
for (int i = 1; i <= n; i++) {
if (arrEdge[i] != 0) {
E[arrEdge[i]].crit = true;
}
}
}
void dijk2(int dest, vector<ll>& dist) {
dist.assign(n + 5, INF);
vector<bool> vis(n + 5, false);
typedef pair<ll, int> pli;
priority_queue<pli, vector<pli>, greater<pli>> Q;
dist[dest] = 0;
vector<int> arrEdge(n + 5, 0);
for (int k = 1; k <= n; k++) {
int a = -1;
ll min = INF;
for (int i = 1; i <= n; i++) {
if (!vis[i] && dist[i] < min) {
a = i;
min = dist[i];
}
}
if (a == -1) break;
vis[a] = true;
for (int b = 1; b <= n; b++) {
int eg = get_edge(b, a, -1);
if (eg == -1) continue;
if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
dist[b] = dist[a] + E[eg].wcost;
arrEdge[b] = eg;
}
}
}
for (int i = 1; i <= n; i++) {
if (arrEdge[i] != 0) {
E[arrEdge[i]].crit = true;
}
}
}
void dijk3(int source, vector<ll>& dist, int swapEg) {
dist.assign(n + 5, INF);
vector<bool> vis(n + 5, false);
typedef pair<ll, int> pli;
priority_queue<pli, vector<pli>, greater<pli>> Q;
dist[source] = 0;
for (int k = 1; k <= n; k++) {
int a = -1;
ll min = INF;
for (int i = 1; i <= n; i++) {
if (!vis[i] && dist[i] < min) {
a = i;
min = dist[i];
}
}
if (a == -1) break;
vis[a] = true;
for (int b = 1; b <= n; b++) {
int eg = get_edge(a, b, swapEg);
if (eg == -1) continue;
if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
dist[b] = dist[a] + E[eg].wcost;
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> E[i].fr >> E[i].to >> E[i].wcost >> E[i].scost;
E[i].crit = false;
// v[E[i].fr].push_back(i);
// v2[E[i].to].push_back(i);
}
adj.assign(n + 5, vector<int>(n + 5, -1));
adj2.assign(n + 5, vector<int>(n + 5, -1));
for (int i = 1; i <= m; i++) {
if (adj[E[i].fr][E[i].to] == -1) {
adj[E[i].fr][E[i].to] = i;
continue;
}
if (adj2[E[i].fr][E[i].to] == -1) {
adj2[E[i].fr][E[i].to] = i;
if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) {
swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]);
}
continue;
}
if (E[i].wcost < E[adj2[E[i].fr][E[i].to]].wcost) {
adj2[E[i].fr][E[i].to] = i;
if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) {
swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]);
}
}
}
vector<ll> distfr1, distton, distfrn, distto1;
dijk(1, distfr1);
dijk(n, distfrn);
dijk2(1, distto1);
dijk2(n, distton);
// cout << "!!!" << endl;
// for (int i = 1; i <= n; i++) {
// cout << i << " " << distfr1[i] << endl;
// }
// cout << "!!!" << endl;
// for (int i = 1; i <= n; i++) {
// cout << i << " " << distfrn[i] << endl;
// }
// cout << "!!!" << endl;
// for (int i = 1; i <= n; i++) {
// cout << i << " " << distto1[i] << endl;
// }
// cout << "!!!" << endl;
// for (int i = 1; i <= n; i++) {
// cout << i << " " << distton[i] << endl;
// }
// cout << "!!!" << endl;
ll ans = INF;
ans = min(ans, distfr1[n] + distfrn[1]);
for (int i = 1; i <= m; i++) {
if (E[i].crit) continue;
ll tmp = min(distfr1[n], distfr1[E[i].to] + E[i].wcost + distton[E[i].fr]);
ll tmp2 = min(distfrn[1], distfrn[E[i].to] + E[i].wcost + distto1[E[i].fr]);
// cout << i << " " << tmp + tmp2 << "\n";
ans = min(ans, tmp + tmp2 + E[i].scost);
}
// cout << ans << endl;
for (int i = 1; i <= m; i++) {
if (!E[i].crit) continue;
vector<ll> dist2fr1(n + 5, INF), dist2frn(n + 5, INF);
dijk3(1, dist2fr1, i);
dijk3(n, dist2frn, i);
ans = min(ans, dist2fr1[n] + dist2frn[1] + E[i].scost);
}
if (ans == INF) ans = -1;
cout << ans << endl;
}
