#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5e4 + 10;
const long long inf = 1e15;
struct vertex {
int node;
long long dist;
vertex (int node, long long dist) : node(node), dist(dist) {}
vertex () {}
bool operator < (vertex v) const {
return dist > v.dist;
}
};
bool del[maxm];
int l[maxm], r[maxm], w[maxm], c[maxm];
int n, m;
vector <int> g[maxn];
vector <long long> shortest_path(int src, bool rev = false) {
vector <long long> d (n, inf);
priority_queue <vertex> Q;
Q.emplace(src, 0);
d[src] = 0;
while(not Q.empty()) {
auto x = Q.top();
Q.pop();
if(x.dist != d[x.node]) continue;
for(int e : g[x.node]) {
if(del[e]) continue;
if(rev && l[e] == x.node) continue;
if(!rev && r[e] == x.node) continue;
int y = l[e] ^ r[e] ^ x.node;
// cout << x.node << " " << y << endl;
if(d[y] > x.dist + w[e]) {
d[y] = x.dist + w[e];
Q.emplace(y, d[y]);
}
}
}
return d;
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> l[i] >> r[i] >> w[i] >> c[i];
l[i] -= 1;
r[i] -= 1;
g[l[i]].push_back(i);
g[r[i]].push_back(i);
}
vector <long long> srcPath (m, inf), desPath(m, inf);
vector <long long> leftSrc (m, inf), srcRight (m, inf);
vector <long long> leftDes (m, inf), desRight (m, inf);
for(int i = 0; i < m; i++) {
del[i] = true;
auto u = shortest_path(0);
auto v = shortest_path(n - 1);
srcRight[i] = u[r[i]];
desRight[i] = v[r[i]];
// cout << i << " " << r[i] << " " << v[r[i]] << endl;
srcPath[i] = u[n - 1];
desPath[i] = v[0];
u = shortest_path(0, true);
v = shortest_path(n - 1, true);
leftSrc[i] = u[l[i]];
leftDes[i] = v[l[i]];
del[i] = false;
}
long long ans = shortest_path(0)[n - 1] + shortest_path(n - 1)[0];
for(int i = 0; i < m; i++) {
long long res = c[i];
res += min(srcRight[i] + w[i] + leftDes[i], srcPath[i]);
res += min(desRight[i] + w[i] + leftSrc[i], desPath[i]);
ans = min(ans, res);
}
if(ans >= inf) ans = -1;
cout << ans << endl;
return 0;
}
