#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define MAXN 17//207
ll a,b,c,d,t,n,m,ans,l;
vector<pair<pair<ll,ll>,pair<ll,ll>>>v;
vector<ll>g[207],g2[207],pth;
bool odw[207];
ll edg[207],dst[207],dst2[207];
ll dst3[207],dst4[207],dst5[207];
vector<ll>g3[207];
ll check(ll x){
a=INFL;
b=INFL;
for(ll i=0;i<207;i++)g3[i].clear();
swap(v[x].ff.ff,v[x].ff.ss);
for(ll i=0;i<m;i++){
g3[v[i].ff.ff].pb(i);
}
for(ll i=0;i<207;i++)dst3[i]=INFL;
dst3[1]=0;
for(ll i=0;i<n;i++){
pair<ll,ll> bst={INFL,-1};
for(ll j=1;j<=n;j++){
if(dst3[j]!=-1)
bst=min(bst,{dst3[j],j});
}
if(bst.ss==n){
a=bst.ff;
break;
}
for(ll j : g3[bst.ss]){
dst3[v[j].ff.ss]=min(dst3[v[j].ff.ss],dst3[bst.ss]+v[j].ss.ff);
}
dst3[bst.ss]=-1;
}
for(ll i=0;i<207;i++)dst3[i]=INFL;
dst3[n]=0;
for(ll i=0;i<n;i++){
pair<ll,ll> bst={INFL,-1};
for(ll j=1;j<=n;j++){
if(dst3[j]!=-1)
bst=min(bst,{dst3[j],j});
}
if(bst.ss==1){
b=bst.ff;
break;
}
for(ll j : g3[bst.ss]){
dst3[v[j].ff.ss]=min(dst3[v[j].ff.ss],dst3[bst.ss]+v[j].ss.ff);
}
dst3[bst.ss]=-1;
}
swap(v[x].ff.ff,v[x].ff.ss);
//cout<<a<<" "<<b<<"\n";
return a+b+v[x].ss.ss;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(ll i=0;i<207;i++){
dst[i]=INFL;
dst2[i]=INFL;
dst3[i]=INFL;
dst4[i]=INFL;
dst5[i]=INFL;
}
for(ll i=0;i<m;i++){
cin>>a>>b>>c>>d;
v.pb({{a,b},{c,d}});
g[a].pb(i);
g2[b].pb(i);
}
v.pb({{-1,1},{0,0}});
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;//koszt,edge
pq.push({0,m});
ans=INFL;
for(ll i=0;i<=n;i++)edg[i]=m;
while(pq.size()){
auto pom=pq.top();
pq.pop();
if(odw[v[pom.ss].ff.ss])continue;
if(v[pom.ss].ff.ss==n)ans=pom.ff;
dst5[v[pom.ss].ff.ss]=pom.ff;
odw[v[pom.ss].ff.ss]=1;
edg[v[pom.ss].ff.ss]=pom.ss;
for(ll i : g[v[pom.ss].ff.ss]){
pq.push({pom.ff+v[i].ss.ff,i});
}
}
ll ak=n;
for(ll i=1;i<=n;i++){
// cout<<edg[i]<<" "<<flush;
}//return 0;
if(edg[n]!=m)
while(ak!=1){
pth.pb(edg[ak]);
//cout<<pth.back()<<" ";
ak=v[edg[ak]].ff.ff;
}//return 0;
sort(pth.begin(),pth.end());
v.back().ff.ss=n;
pq.push({0,m});
for(ll i=0;i<=n;i++)edg[i]=m;
for(ll i=0;i<207;i++)odw[i]=0;
while(pq.size()){
auto pom=pq.top();
pq.pop();
if(odw[v[pom.ss].ff.ss])continue;
dst[v[pom.ss].ff.ss]=pom.ff;
odw[v[pom.ss].ff.ss]=1;
edg[v[pom.ss].ff.ss]=pom.ss;
for(ll i : g[v[pom.ss].ff.ss]){
pq.push({pom.ff+v[i].ss.ff,i});
}
}
ak=1;
for(ll i=1;i<=n;i++){
// cout<<edg[i]<<" "<<flush;
}
if(edg[1]!=m)
while(ak!=n){
pth.pb(edg[ak]);
//cout<<pth.back()<<" ";
ak=v[edg[ak]].ff.ff;
}
v.back().ff={1,-1};
pq.push({0,m});
for(ll i=0;i<207;i++)odw[i]=0;
while(pq.size()){
auto pom=pq.top();
pq.pop();
if(odw[v[pom.ss].ff.ff])continue;
dst2[v[pom.ss].ff.ff]=pom.ff;
odw[v[pom.ss].ff.ff]=1;
for(ll i : g2[v[pom.ss].ff.ff]){
pq.push({pom.ff+v[i].ss.ff,i});
}
}
v.back().ff={n,-1};
pq.push({0,m});
for(ll i=0;i<207;i++)odw[i]=0;
while(pq.size()){
auto pom=pq.top();
pq.pop();
if(odw[v[pom.ss].ff.ff])continue;
dst4[v[pom.ss].ff.ff]=pom.ff;
odw[v[pom.ss].ff.ff]=1;
for(ll i : g2[v[pom.ss].ff.ff]){
pq.push({pom.ff+v[i].ss.ff,i});
}
}
ans+=dst[1];
sort(pth.begin(),pth.end());
// cout<<ans<<" ";
// cout<<dst5[n]<<" "<<dst[1]<<"\n";
for(ll i=0;i<m;i++){
if(lower_bound(pth.begin(),pth.end(),i)!=pth.end() && *lower_bound(pth.begin(),pth.end(),i)==i)continue;
// return 0;
// cout<<i<<" ";
// cout<<ans<<" ";
// cout<<ans<<" "<<v[i].ss.ff+dst4[v[i].ff.ff]+dst5[v[i].ff.ss]<<"\n";//return 0;
ans=min(ans,min(dst5[n],v[i].ss.ff+dst4[v[i].ff.ff]+dst5[v[i].ff.ss])+min(dst[1],v[i].ss.ff+dst2[v[i].ff.ff]+dst[v[i].ff.ss])+v[i].ss.ss);
//return 0;
}//return 0;
//cout<<ans<<" ";
for(ll i : pth){
//cout<<v[i].ss.ff<<" "<<v[i].ss.ss<<"\n";
// cout<<i<<" ";
ans=min(ans,check(i));
//cout<<ans<<" ";
}
if(ans>=INFL)ans=-1;
cout<<ans;
// cout<<"\n";
for(ll i=0;i<n;i++){
// cout<<dst[i+1]<<" "<<dst2[i+1]<<" "<<dst3[i+1]<<" "<<dst4[i+1]<<" "<<dst5[i+1]<<"\n";
}
return 0;
}
