#include<bits/stdc++.h>
using namespace std;
const long long maxn = 210;
const long long maxm = 5e4 + 10;
const long long inf = 1e18;
struct matrix{
long long n, m;
long long a[maxn][maxn];
matrix(long long N, long long M){
n = N;
m = M;
for(long long i = 0; i < n; i++)
for(long long j = 0; j < m; j++)
a[i][j] = inf;
}
matrix operator * (matrix & oth){
matrix ans = matrix(n, n);
for(long long i = 0; i < n; i++){
for(long long j = 0; j < n; j++){
ans.a[i][j] = min(a[i][j], oth.a[i][j]);
for(long long k = 0; k < n; k++)
ans.a[i][j] = min(ans.a[i][j], a[i][k] + oth.a[k][j]);
}
}
return ans;
}
};
long long n, m;
long long from[maxm];
long long to[maxm];
long long D[maxm];
long long weight[maxm];
long long ans;
matrix a = matrix(0, 0);
matrix b = matrix(0, 0);
multiset<long long> BOI[maxn][maxn];
void in();
void solve();
void rsolve(long long x);
void out();
int main(){
in();
solve();
out();
}
void in(){
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
cin >> n >> m;
for(long long i = 0; i < m; i++){
long long u, v, w, d;
cin >> u >> v >> w >> d;
u--;
v--;
from[i] = u;
to[i] = v;
D[i] = d;
weight[i] = w;
BOI[u][v].insert(w);
}
}
void solve(){
ans = inf;
a = matrix(n, n);
for(long long i = 0; i < n; i++){
for(long long j = 0; j < n; j++){
BOI[i][j].insert(inf);
a.a[i][j] = *BOI[i][j].begin();
}
}
b = a;
rsolve(0);
for(long long i = 0; i < m; i++){
b = a;
long long u = from[i];
long long v = to[i];
BOI[u][v].erase(BOI[u][v].find(weight[i]));
BOI[v][u].insert(weight[i]);
b.a[u][v] = *BOI[u][v].begin();
b.a[v][u] = *BOI[v][u].begin();
rsolve(D[i]);
BOI[v][u].erase(BOI[v][u].find(weight[i]));
BOI[u][v].insert(weight[i]);
}
if(ans == inf)
ans = -1;
}
void rsolve(long long x){
for(long long i = 0; i < 20; i++)
b = b * b;
ans = min(ans, b.a[0][n - 1] + b.a[n - 1][0] + x);
}
void out(){
cout << ans;
}
