/***Farhan132***/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define clean fflush(stdout)
const ll mod = (ll)1e9 + 7;
const ll maxn = (ll)2e5 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
//const ll INF = 1e18;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
struct edge{
ll x, y , cost, r , id;
};
struct thing{
ll D , p , e;
ll vis;
};
ll n , m;
vector < edge > g;
vector < edge > v[205] , rev[205];
set < ll > cool;
ll par[10][205];
ll f[10][205];
ll dis[10][205];
edge W;
thing t[205];
void shortest(ll x, ll w, ll lol, edge kk){
if(lol != -1) for(ll i = 1; i <= n; i++) dis[w][i] = -1;
for(ll i = 1; i <= n; i++){
t[i].D = 1e18;
t[i].p = -1;
t[i].e = -1;
t[i].vis = 0;
par[w][i] = -1;
}
t[x].D = 0;
while(1){
thing final;
final.D = 1e18;
ll node = -1;
for(ll i = 1; i <= n; i++){
if(t[i].vis) continue;
if(t[i].D < final.D) final = t[i] , node = i;
}
if(node == -1) break;
dis[w][node] = t[node].D;
par[w][node] = t[node].p;
f[w][node] = t[node].e;
t[node].vis = 1;
if(w <= 1){
for(edge u : v[node]){
if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost ) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0};
}
}else if(w <= 3){
for(edge u : rev[node]){
if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost ) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0};
}
}else if(w <= 5){
for(edge u : v[node]){
if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost && u.id != lol) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0};
}
if(kk.x == node && !t[kk.y].vis && t[kk.y].D > dis[w][node] + kk.cost + kk.r) t[kk.y] = {dis[w][node] + kk.cost + kk.r, node , kk.id , 0};
}
}
if(w >= 2) return;
ll cur = 1;
if(x == 1) cur = n;
if(dis[w][cur] == -1) return;
ll cnt = 0;
while(1){
if(par[w][cur] == -1) break;
cool.in(f[w][cur]);
cur = par[w][cur];
}
return;
}
void solve(){
cin >> n >> m;
for(ll i = 1; i <= m; i++){
ll x , y , cost , r;
cin >> x >> y >> cost >> r;
v[x].pb({x,y,cost,r,i});
rev[y].pb({y,x,cost,r,i});
g.pb({x,y,cost,r,i});
}
mem(dis,-1);
shortest(1, 0, -1, W);
shortest(n, 1, -1, W);
shortest(1, 2, -1, W);
shortest(n, 3, -1, W);
ll ans = 1e18;
if(dis[0][n] != -1 && dis[1][1] != -1) ans = dis[1][1] + dis[0][n];
for(edge u : g){
if(cool.count(u.id)){
edge passing;
passing = u;
passing.y = u.x;
passing.x = u.y;
shortest(1, 4, u.id, passing);
shortest(n, 5, u.id, passing);
if(dis[4][n] == -1 || dis[5][1] == -1) continue;
ans = min(ans , dis[4][n] + dis[5][1]);
}else{
ll X = 1e18 , Y = 1e18;
if(dis[0][n] != -1) X = dis[0][n];
if(dis[1][1] != -1) Y = dis[1][1];
if(dis[0][u.y] != -1 && dis[3][u.x] != -1) X = min(X , dis[0][u.y] + dis[3][u.x] + u.cost );
if(dis[1][u.y] != -1 && dis[2][u.x] != -1) Y = min(Y, dis[1][u.y] + dis[2][u.x] + u.cost );
ans = min(ans , X + Y + u.r);
}
}
if(ans == 1e18) ans = -1;
cout << ans;
return;
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
// freopen("cbarn2.in", "r", stdin);
// freopen("cbarn2.out", "w", stdout);
// ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#endif
//cout << fixed << setprecision(10);
// work(maxn);
// mem(b,0);
ll T;
T=1;
//cin >> T;
//scanf("%lld",&T);
// ll CT = 0;
//work();
while(T--){
//cout << "Case " << ++CT <<": " ;
//printf("Case %lld: ",++CT);
solve();
}
return 0;
}
