//抄解因為我笨，根本就不會最短路徑樹
//煩躁實作
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fs first
#define sc second
const int inf = 1e18, binf = inf + 11e9;
pii es[50100];
int n, m, C[50100], D[50100], ontree[50100] = {0};
vector <int> ans1n, ansn1, tree1n, treen1, e[210][210];
vector <int> ansxn[210], ansx1[210];
bool notused[50100] = {0};
pair< vector<int>, vector<int> > Dijkstra(int st, int ed);
int solve (int ei) {
if (ontree[ei]) {
notused[ei] = 1;
e[es[ei].sc][es[ei].fs] . push_back(m + 1);
C[m + 1] = C[ei], D[m + 1] = D[ei];
int res = Dijkstra(1, n).fs[n];
res += Dijkstra(n, 1).fs[1] + D[ei];
notused[ei] = 0;
e[es[ei].sc][es[ei].fs] . pop_back();
return res;
}
else {
int res = ans1n[n] + ansn1[es[ei].sc] + ansx1[es[ei].fs][1] + C[ei] + D[ei];
res = min(ans1n[es[ei].sc] + ansxn[es[ei].fs][n] + ansn1[1] + C[ei] + D[ei], res);
res = min(ans1n[es[ei].sc] + ansxn[es[ei].fs][n] + ansn1[es[ei].sc] + ansx1[es[ei].fs][1] + C[ei] * 2 + D[ei], res);
return res;
}
}
pair< vector<int>, vector<int> > Dijkstra(int st, int ed) {
vector <int> ans(n + 2, binf), vis(n + 2, 0), tree, from(n + 2, 0);
ans[st] = 0;
for (int t = 0; t <= n; t++) {
int ii = 1;
for (int i = 1; i <= n; i++) if (!vis[i]) ii = i;
for (int i = 1; i <= n; i++) if (!vis[i] and ans[i] < ans[ii]) ii = i;
if (vis[ii] or ans[ii] > inf) break;
vis[ii] = 1;
for (int j = 1; j <= n; j++) {
if (vis[j] or !e[ii][j].size()) continue;
for (int ei : e[ii][j] ) {
if (notused[ei]) continue;
if (ans[ii] + C[ei] < ans[j]) {
ans[j] = ans[ii] + C[ei];
from[j] = ei;
}
}
}
}
for (int i = 1; i <= n; i++) if(i != st) tree.push_back(from[i]);
return {ans, tree};}
signed main () {
ios_base :: sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> es[i].fs >> es[i].sc >> C[i] >> D[i];
e[es[i].fs][es[i].sc].push_back(i);
}
auto rEs = Dijkstra (1, n);
ans1n = rEs.fs, tree1n = rEs.sc;
rEs = Dijkstra (n, 1);
ansn1 = rEs.fs, treen1 = rEs.sc;
for (int x : tree1n) ontree[x] = 1;
for (int x : treen1) ontree[x] = 1;
for (int i = 1; i <= n; i++) ansxn[i] = Dijkstra (i, n).fs, ansx1[i] = Dijkstra (i, 1).fs;
int finans = ans1n[n] + ansn1[1];
for (int i = 0; i < m; i++) finans = min(finans, solve(i));
if (finans >= inf) finans = -1;
cout << finans << '\n';
return 0;}
