#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn =2e5+30;
const ll mod=1e9+7 ;
const ll base=1e18;
ll x[maxn];
ll y[maxn];
ll c[maxn];
ll d[maxn];
vector<ll> adj[maxn][2];
ll dp[maxn][6];
ll pre[maxn];
ll n, m ;
bool dd[maxn];
void dosth(ll p,ll type,ll ta,ll rc,ll t)
{
priority_queue<pll,vector<pll>,greater<pll>> q;
for (int i=1; i<=n; i++)
{
dp[i][type]=base;
}
dp[p][type]=0;
q.push(make_pair(dp[p][type],p));
while (!q.empty())
{
auto p=q.top();
q.pop();
ll u=p.ss;
if (dp[u][type]!=p.ff)
continue;
for (auto to:adj[u][ta])
{
if (u==rc&&to==t)
continue;
ll nxt=x[to]+y[to]-u;
if (dp[nxt][type]>dp[u][type]+c[to])
{
dp[nxt][type]=dp[u][type]+c[to];
q.push(make_pair(dp[nxt][type],nxt));
pre[nxt]=to;
}
}
}
}
void dosth1()
{
dosth(1,0,0,-1,-1);
ll nw=n;
while (nw!=1)
{
// cout <<nw<<" "<<pre[nw]<<endl;
dd[pre[nw]]=1;
nw=x[pre[nw]]+y[pre[nw]]-nw;
}
dosth(1,1,1,-1,-1);
dosth(n,2,0,-1,-1);
dosth(n,3,1,-1,-1);
ll ans=dp[n][0]+dp[n][1];
for (int i=1; i<=m; i++)
{
if (dd[i])
{
ll h1=x[i];
ll h2=y[i];
adj[h2][0].pb(i);
swap(x[i],y[i]);
dosth(1,4,0,h1,i);
ll h=dp[n][4]+d[i];
dosth(n,4,0,h1,i);
h+=dp[1][4];
swap(x[i],y[i]);
adj[h2][0].pop_back();
ans=min(ans,h);
}
else
{
ans=min(ans,dp[n][0]+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]);
/* if (min(dp[n][0],dp[y[i]][0]+dp[x[i]][3])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]==1)
{
cout <<i<<endl;
}*/
}
}
if (ans>=base)
{
ans=-1;
}
cout <<ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("graph.inp","r"))
{
freopen("graph.inp","r",stdin);
freopen("graph.out","w",stdout);
}
cin>> n>> m;
for (int i=1; i<=m; i++)
{
cin>>x[i]>> y[i]>>c[i]>> d[i ];
adj[x[i]][0].pb(i);
adj[y[i]][1].pb(i);
}
dosth(1,0,0,-1,-1);
// cout <<dp[n][0]<<endl;
if (dp[n][0]!=base)
{
dosth1();
}
else
{
dosth(n,0,0,-1,-1);
if (dp[1][0]!=base)
{
for (int i=1; i<=n; i++)
{
adj[i][0].clear();
adj[i][1].clear();
}
for (int i=1; i<=m; i++)
{
if (x[i]==n)
x[i]=1;
else if (x[i]==1) x[i]=n;
if (y[i]==n)
y[i]=1;
else if (y[i]==1) y[i]=n;
// cout <<x[i]<< " "<<y[i]<<endl;
adj[x[i]][0].pb(i);
adj[y[i]][1].pb(i);
}
dosth1();
}
else
{
dosth(1,0,0,-1,-1);
dosth(1,1,1,-1,-1);
dosth(n,2,0,-1,-1);
dosth(n,3,1,-1,-1);
ll ans=dp[n][0]+dp[n][1];
for (int i=1; i<=m; i++)
{
ans=min(ans,dp[y[i]][0]+dp[x[i]][3]+dp[y[i]][2]+dp[x[i]][1]+d[i]+2*c[i]);
}
if (ans>=base)
{
ans=-1;
}
cout <<ans;
}
}
}
