#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int MXN = 205, MXM = 50005;
vector<pair<pair<int, int>, pair<int, int>>> eds;
vector<pair<pair<int, int>, pair<int, int>>> adj[MXN];
int par[MXN];
int parof[MXN];
int dist1n[MXM];
int distn1[MXM];
int dist[MXN];
bool onpath[MXM];
bool onpath2[MXM];
vector<int> path;
int block = -1;
int mxh = INT_MAX * 200ll;
int get_dist(int src, int dest, int blo) {
block = blo;
memset(onpath, 0, sizeof onpath);
for (int i=1; i<=n; i++) {
dist[i] = mxh;
par[i] = -1;
parof[i] = -1;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
proc.push({0, src});
while (!proc.empty()) {
pair<int, int> tr = proc.top();
proc.pop();
int no = tr.second;
int di = tr.first;
if (dist[no] < di) continue;
dist[no] = di;
for (auto x: adj[no]) {
int ad = x.first.first;
int ind = x.first.second;
int we = x.second.first;
if (ind == block) continue;
if (dist[no] + we < dist[ad]) {
dist[ad] = dist[no] + we;
par[ad] = ind;
parof[ad] = no;
proc.push({dist[ad], ad});
}
}
}
vector<int> tr;
tr.push_back(-1);
path = tr;
tr.clear();
int x = dest;
while (x != src) {
if (x == -1) return dist[dest];
tr.push_back(x);
onpath[par[x]] = true;
x = parof[x];
}
tr.push_back(src);
reverse(tr.begin(), tr.end());
path = tr;
return dist[dest];
}
signed main() {
cin >> n >> m;
for (int i=0; i<m; i++) {
int a, b, w, f;
cin >> a >> b >> w >> f;
adj[a].push_back({{b, i}, {w, f}});
eds.push_back({{a, b}, {w, f}});
}
{
int wh = get_dist(1, n, -1);
dist1n[m] = wh;
int apsp[n+1][n+1], apsp_exc[n+1][n+1];
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
apsp[i][j] = mxh;
apsp_exc[i][j] = mxh;
if (i == j) apsp[i][j] = apsp_exc[i][j] = 0;
}
}
for (int i=0; i<m; i++) {
int a = eds[i].first.first, b = eds[i].first.second;
int w = eds[i].second.first;
apsp[a][b] = min(apsp[a][b], w);
if (!onpath[i]) {
apsp_exc[a][b] = min(apsp_exc[a][b], w);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
apsp[i][j] = apsp[i][k] + apsp[k][j];
}
if (apsp_exc[i][k] + apsp_exc[k][j] < apsp_exc[i][j]) {
apsp_exc[i][j] = apsp_exc[i][k] + apsp_exc[k][j];
}
}
}
}
for (int i=0; i<m; i++) {
int a = eds[i].first.first, b = eds[i].first.second;
int w = eds[i].second.first;
if (onpath[i]) {
dist1n[i] = mxh;
if (path[0] != -1) {
for (int i=0; i<path.size(); i++) {
for (int j=i+1; j<path.size(); j++) {
dist1n[i] = min(dist1n[i], apsp[1][path[i]] + apsp_exc[path[i]][path[j]] + apsp[path[j]][n]);
}
}
}
}
else {
dist1n[i] = wh;
dist1n[i] = min(dist1n[i], apsp[1][b] + w + apsp[a][n]);
}
}
}
{
int wh = get_dist(n, 1, -1);
distn1[m] = wh;
int apsp[n+1][n+1], apsp_exc[n+1][n+1];
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
apsp[i][j] = mxh;
apsp_exc[i][j] = mxh;
if (i == j) apsp[i][j] = apsp_exc[i][j] = 0;
}
}
for (int i=0; i<m; i++) {
int a = eds[i].first.first, b = eds[i].first.second;
int w = eds[i].second.first;
apsp[a][b] = min(apsp[a][b], w);
if (!onpath[i]) {
apsp_exc[a][b] = min(apsp_exc[a][b], w);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
apsp[i][j] = apsp[i][k] + apsp[k][j];
}
if (apsp_exc[i][k] + apsp_exc[k][j] < apsp_exc[i][j]) {
apsp_exc[i][j] = apsp_exc[i][k] + apsp_exc[k][j];
}
}
}
}
for (int i=0; i<m; i++) {
int a = eds[i].first.first, b = eds[i].first.second;
int w = eds[i].second.first;
if (onpath[i]) {
distn1[i] = mxh;
if (path[0] != -1) {
for (int i=0; i<path.size(); i++) {
for (int j=i+1; j<path.size(); j++) {
distn1[i] = min(distn1[i], apsp[n][path[i]] + apsp_exc[path[i]][path[j]] + apsp[path[j]][1]);
}
}
}
}
else {
distn1[i] = wh;
distn1[i] = min(distn1[i], apsp[n][b] + w + apsp[a][1]);
}
}
}
int best = dist1n[m] + distn1[m];
for (int i=0; i<m; i++) {
int ix = dist1n[i] + distn1[i] + eds[i].second.second;
best = min(best, ix);
}
if (best > mxh) cout << -1 << endl;
else cout << best << endl;
}
