// In the name of Allah
// There is no power but from God the Almighty
// No God except Allah
#include <bits/stdc++.h>
#define mp make_pair
#define f1 first
#define f2 second
#define pb push_back
#define pii pair<int ,int>
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mox=2e2+9;
vector<pair< pair<int , long long > ,int > > v[mox][2];
bool ok[50009];
set<pii> s;
long long d[mox][17*mox];
int dad[mox][17*mox];
long long po[50009];
vector<pair<pii , int > > g;
int n,m;
void dj(int o,int y ,int no,int q)
{
s.insert({0,y});
for(int i=1 ; i<=n ; i++)
d[i][o]=1e10;
d[y][o]=0;
while(s.empty()==0)
{
int x=s.begin()->f2;
s.erase(s.begin());
for(pair<pii,int> i:v[x][q])
{
if(d[i.f1.f1][o]>d[x][o]+i.f1.f2&&i.f2!=no)
{
s.erase({d[i.f1.f1][o],i.f1.f1});
d[i.f1.f1][o]=d[x][o]+i.f1.f2;
s.insert({d[i.f1.f1][o],i.f1.f1});
dad[i.f1.f1][o]=i.f2;
}
}
}
}
main()
{ ios
int subbbb;
cin>>n>>m;
for(int i=0 ; i<m ; i++)
{
int a,b,c,e;
cin>>a>>b>>c>>e;
v[a][0].pb({{b,c},i});
v[b][1].pb({{a,c},i});
po[i]=e;
g.pb({{a,b},c});
}
dj(0,1,-1,0);
dj(1,n,-1,0);
dj(2,1,-1,1);
dj(3,n,-1,1);
for(int j=1 ; j<=n ; j++)
{
ok[dad[j][0]]=1;
ok[dad[j][1]]=1;
ok[dad[j][2]]=1;
ok[dad[j][3]]=1;
}
long long ans=d[1][1]+d[n][0];
int w=4;
for(int i=0 ; i<m ; i++)
{
if(ok[i]==1)
{
dj(w,1,i,0);
w++;
dj(w,n,i,0);
w++;
dj(w,1,i,1);
w++;
dj(w,n,i,1);
w++;
long long x=d[g[i].f1.f2][w-4]+d[g[i].f1.f1][w-1]+g[i].f2;
long long y=d[g[i].f1.f2][w-3]+d[g[i].f1.f1][w-2]+g[i].f2;
long long p=(x+y+po[i]);
ans=min(ans,p);
ans=min(x+d[1][w-3]+po[i],ans);
ans=min(y+d[n][w-4]+po[i],ans);
}
else
{
long long x=d[g[i].f1.f2][0]+d[g[i].f1.f1][3]+g[i].f2;
long long y=d[g[i].f1.f2][1]+d[g[i].f1.f1][2]+g[i].f2;
long long p=(x+y+po[i]);
ans=min(ans,p);
ans=min(x+d[1][1]+po[i],ans);
ans=min(y+d[n][0]+po[i],ans);
}
}
if(ans<1e10)
cout<<ans;
else
cout<<-1;
}
