#include <bits/stdc++.h>
using namespace std;
#define task "main"
#define F first
#define S second
#define ii pair<int, int>
#define il pair<int, long long>
#define li pair<long long, int>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
const int MAX_N = (int)203;
const int MAX_M = (int)5e4+ 4;
const long long INF = (long long)1e18;
int nNode, nEdge;
long long firstMin[MAX_N][MAX_N], secondMin[MAX_N][MAX_N];
struct EDGE {
int u, v, cost, revCost;
} edges[MAX_M];
long long dist[2][MAX_N], revDist[2][MAX_N], tmpDist[2][MAX_N];
bool isKey[MAX_N][MAX_N], visited[MAX_N], used[MAX_N][MAX_N];
int parent[MAX_N];
void dijkstra(int u, long long *d, short type) {
FOR(i, 0, nNode) d[i] = INF, parent[i] = 0, visited[i] = false;
d[u] = 0;
while (true) {
int u = 0;
FOR(i, 1, nNode) if (!visited[i] && d[i] < d[u])
u = i;
if (!u) break;
visited[u] = true;
FOR(v, 1, nNode) if (!visited[v])
if (minimize(d[v], d[u] + (type == 1 ? firstMin[v][u] : firstMin[u][v])))
if (type < 2)
parent[v] = u;
}
if (type < 2) {
FOR(u, 1, nNode) isKey[parent[u]][u] = true;
}
}
void solve() {
memset(firstMin, 0x3f, sizeof(firstMin));
memset(secondMin, 0x3f, sizeof(secondMin));
cin >> nNode >> nEdge;
FOR(i, 1, nEdge) {
int u, v, c, d;
cin >> u >> v >> c >> d;
if (firstMin[u][v] > c) {
secondMin[u][v] = firstMin[u][v];
firstMin[u][v] = c;
}
else if (secondMin[u][v] > c)
secondMin[u][v] = c;
edges[i] = {u, v, c, d};
}
dijkstra(1, dist[0], 0);
dijkstra(nNode, dist[1], 0);
dijkstra(1, revDist[0], 1); // 1: reverse edges
dijkstra(nNode, revDist[1], 1);
long long ans = dist[0][nNode] + dist[1][1];
FOR(i, 1, nEdge) {
auto [u, v, cost, changeCost] = edges[i];
if (!used[u][v] && isKey[u][v] && cost == firstMin[u][v]) {
used[u][v] = true;
// reverse edge u->v
long long preUV = firstMin[u][v], preVU = firstMin[v][u];
minimize(firstMin[v][u], cost);
firstMin[u][v] = secondMin[u][v];
dijkstra(1, tmpDist[0], 2);
dijkstra(nNode, tmpDist[1], 2);
minimize(ans, tmpDist[0][nNode] + tmpDist[1][1] + changeCost);
firstMin[u][v] = preUV, firstMin[v][u] = preVU;
}
else {
minimize(ans, changeCost + min(dist[0][nNode], dist[0][v] + cost + revDist[1][u]) +
min(dist[1][1], revDist[0][u] + cost + dist[1][v]));
}
}
cout << (ans >= INF ? -1 : ans);
}
int32_t main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
bool multitest = 0;
int numTest = 1;
if (multitest) cin >> numTest;
while (numTest--) {
solve();
}
return 0;
}
/* Lak lu theo dieu nhac!!!! */
