#include "bits/stdc++.h"
using namespace std;
long long d[222][222];
vector <int> g[222], t[222];
int l[50010], r[50010], c[50010], db[50010];
int n, m;
const long long inf = 1e16;
struct data {
int node;
long long dist;
data (int node, long long dist) : node(node), dist(dist) {}
data () {}
bool operator < (data d) const {
return dist > d.dist;
}
};
vector <long long> shortest_path(int src, int del) {
priority_queue <data> Q;
Q.push(data(src, 0));
vector <long long> dist (n + 1, inf);
dist[src] = 0;
while(!Q.empty()) {
data u = Q.top();
Q.pop();
for(auto e : g[u.node]) {
if(e == del) continue;
int y = r[e];
if(u.dist + c[e] < dist[y]) {
dist[y] = u.dist + c[e];
Q.push(data(y, dist[y]));
}
}
}
return dist;
}
vector <int> path(int u, int v) {
vector <long long> dist (n + 1, inf);
dist[u] = 0;
vector <int> prev (n + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(dist[l[j]] + c[j] < dist[r[j]]) {
dist[r[j]] = dist[l[j]] + c[j];
prev[r[j]] = j;
}
}
}
vector <int> ans;
if(dist[v] >= inf) return ans;
while(u != v) {
ans.push_back(prev[v]);
v ^= l[prev[v]] ^ r[prev[v]];
}
return ans;
}
bool imp[50010];
vector <long long> delpath[50010], delsrc[50010];
long long delEdge(int u, int x, int e) {
long long opt = inf;
for(auto i : t[x]) {
if(i != e) {
opt = min(opt, c[i] + d[u][l[i]]);
}
}
return opt;
}
long long solve(int u, int v) {
long long ans = d[u][v] + d[v][u];
for(int j = 1; j <= m; j++) {
long long p1 = delsrc[j][r[j]] + c[j] + db[j] + d[l[j]][v];
long long p2 = delpath[j][r[j]] + c[j] + d[l[j]][u];
p2 = min(p2, delpath[j][u]);
ans = min(ans, p1 + p2);
}
return ans;
}
void build() {
int u = 1, v = n;
vector <int> can = path(v, u);
memset(imp, false, sizeof imp);
for(int i : can) imp[i] = true;
for(int i = 1; i <= m; i++) {
if(imp[i]) {
delpath[i] = shortest_path(v, i);
} else {
delpath[i].resize(n + 1);
for(int j = 1; j <= n; j++) {
delpath[i][j] = d[v][j];
}
}
}
can = path(u, v);
memset(imp, false, sizeof imp);
for(int i : can) imp[i] = true;
for(int i = 1; i <= m; i++) {
if(imp[i]) {
delsrc[i] = shortest_path(u, i);
} else {
delsrc[i].resize(n + 1);
for(int j = 1; j <= n; j++) {
delsrc[i][j] = d[u][j];
}
}
}
}
int main(int argc, char const *argv[])
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) {
d[i][j] = inf;
}
}
}
for(int i = 1; i <= m; i++) {
scanf("%d %d %d %d", &l[i], &r[i], &c[i], &db[i]);
d[l[i]][r[i]] = min(d[l[i]][r[i]], (long long) c[i]);
g[l[i]].push_back(i);
t[r[i]].push_back(i);
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
build();
long long ans = solve(1, n);
for(int i = 1; i <= m; i++) {
delsrc[i].swap(delpath[i]);
}
ans = min(ans, solve(n, 1));
if(ans >= inf) ans = -1;
printf("%lld\n", ans);
return 0;
}
