// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>
const ll mod = 1e9 + 7;
const int MAXN = 1e5 + 5;
const ll oo = 1e18 + 7;
const int base = 10;
int n, m;
struct canh{
int u, v, c, d, id;
}cc[MAXN];
vector<canh> adj[2][MAXN];
int chk[MAXN];
int f2[MAXN][2];
void dijsktra2(int s){
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
FOR(i, 1, n){
f2[i][0]=f2[i][1]=oo;
}
f2[s][0]=0;
q.push({0, {s, 0}});
while(!q.empty()){
int c=q.top().fi;
auto uu=q.top().se;
int u=uu.fi, t=uu.se;
q.pop();
if(c>f2[u][t]) continue;
for(auto vv:adj[0][u]){
int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
if(f2[v][t]>c+w){
f2[v][t]=c+w;
q.push({f2[v][t], {v, t}});
}
}
if(!t){
for(auto vv:adj[1][u]){
int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
if(chk[id]) continue;
if(f2[v][1]>c+w+d){
f2[v][1]=c+w+d;
q.push({f2[v][1], {v, 1}});
}
}
}
}
}
int f[5][MAXN];
void dijsktra(int s, int t, int tt){
priority_queue<pii, vector<pii>, greater<pii>> q;
FOR(i, 1, n){
f[t][i]=oo;
}
f[t][s]=0;
q.push({0, s});
while(!q.empty()){
int c=q.top().fi, u=q.top().se;
q.pop();
if(c>f[t][u]) continue;
for(auto vv:adj[tt][u]){
int _=vv.u, v=vv.v, w=vv.c, d=vv.d, id=vv.id;
if(chk[id]) continue;
if(f[t][v]>c+w){
f[t][v]=c+w;
q.push({f[t][v], v});
}
}
}
}
int d[205][205];
pii tr[205][205];
void floyd(){
FOR(i, 1, n){
FOR(j, 1, n){
d[i][j]=oo;
if(i==j) d[i][j]=0;
tr[i][j]={0, 0};
}
}
FOR(i, 1, m){
auto vv=cc[i];
int u=vv.u, v=vv.v, c=vv.c, dd=vv.d, id=vv.id;
if(d[u][v]>c){
d[u][v]=c;
tr[u][v]={u, id};
}
}
FOR(k, 1, n){
FOR(u, 1, n){
FOR(v, 1, n){
if(d[u][v]>d[u][k]+d[k][v]){
d[u][v]=d[u][k]+d[k][v];
tr[u][v]=tr[k][v];
}
}
}
}
}
vector<int> trace(int s, int t){
vector<int> trc;
int u=t;
while(u!=s){
trc.push_back(tr[s][u].se);
u=tr[s][u].fi;
}
reverse(trc.begin(), trc.end());
return trc;
}
int solve(int s, int t){
floyd();
if(d[s][t]==oo) return oo;
vector<int> trc=trace(s, t);
// cout << d[s][t] << ' ';
for(auto x:trc){
// cout << x << ' ';
chk[x]=1;
}
dijsktra2(t);
// cout << f2[s][0] << ' ';
int ans=d[s][t]+min(f2[s][0], f2[s][1]);
FOR(i, 1, m){
chk[i]=0;
}
dijsktra(t, 1, 0);
dijsktra(s, 2, 1);
for(auto x:trc){
auto vv=cc[x];
int u=vv.u, v=vv.v, c=vv.c, d=vv.d, id=vv.id;
chk[x]=1;
dijsktra(s, 0, 0);
int cst=f[0][t]+f[1][u]+f[2][v]+c+d;
cst=min(cst, f[0][t]+f[1][v]+f[2][u]+c+d);
ans=min(ans, cst);
chk[x]=0;
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("test.txt", "r", stdin);
// freopen("o2.out", "w", stdout);
if(fopen(".inp", "r")){
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> m;
FOR(i, 1, m){
int u, v, c, d;
cin >> u >> v >> c >> d;
cc[i]={u, v, c, d, i};
adj[0][u].push_back({0, v, c, d, i});
adj[1][v].push_back({0, u, c, d, i});
}
int res;
res=min(solve(1, n), solve(n, 1));
// res=solve(1, n);
if(res==oo) res=-1;
cout << res;
return 0;
}
