#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int32_t,int32_t>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
//#undef int
int n,k,m,d,q;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
vector<pii>adj[202];
vector<pair<int,pii>>e;
int cost[mxn+10];
int dist[202][202][2][2];
//without, at, start from
vector<int>E[202][202];
void dijk(int ban,int x,int y,int z){
priority_queue<pii,vector<pii>,greater<pii>>pq;
for(int i=1;i<=n;i++)dist[ban][i][y][z]=inf;
if(ban==x)return;
dist[ban][x][y][z]=0;
pq.push({0,x});
while(!pq.empty()){
int cur=pq.top().s,C=pq.top().f;
pq.pop();
if(dist[ban][cur][y][z]!=C)continue;
for(auto i:adj[cur])if(i.f!=ban&&(ll)(dist[ban][i.f][y][z])>(ll)(dist[ban][cur][y][z]+i.s)){
dist[ban][i.f][y][z]=dist[ban][cur][y][z]+i.s;
pq.push({dist[ban][i.f][y][z],i.f});
}
}
}
vector<pii>adj2[mxn+10];
vector<int>pref[mxn+10][2],suf[mxn+10][2];
int get(int x,int y,int a,int b,int c,int id){
//get dist with edge a,b,c inverted from x->y
//not use inverted b->a
ll ans=min(dist[a][y][(x==n)][0],dist[b][y][(x==n)][0]);
if(adj2[a].size()>1){
int g=inf;
if(id)g=min(g,pref[a][x==n][id-1]);
if(id+1<adj2[a].size())g=min(g,suf[a][x==n][id+1]);
ans=min(ans,dist[b][a][y==n][1]+g);
}
//use
ans=min(ans,(ll)(dist[b][a][(x==n)][0]+dist[a][b][(y==n)][1]+c));
return ans;
}
int32_t main(){
fastio
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c>>cost[i];
adj2[b].pb({a,i});
E[a][b].pb(c);
e.pb({c,{a,b}});
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
sort(all(E[i][j]));
if(E[i][j].size()){
adj[i].pb({j,E[i][j][0]});
}
}
//2n((n+m)log(n))=2(10^7)log(200)=1.6x10^8
//we can kinda opt the size of m to (n^2) to make it
//=2(8x10^6)log(200)=(1.6x10^7)log(200)=1.28 x 10^8
for(int i=1;i<=n;i++)dijk(i,1,0,0),dijk(i,n,1,0);
for(int i=1;i<=n;i++)adj[i].clear();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(E[i][j].size())adj[j].pb({i,E[i][j][0]});
for(int i=1;i<=n;i++)dijk(i,1,0,1),dijk(i,n,1,1);
int x=inf,y=inf;
ll ans=inf;
for(auto i:adj[n])x=min(x,i.s+dist[n][i.f][0][0]);
for(auto i:adj[1])y=min(y,i.s+dist[1][i.f][1][0]);
ans=min(ans,(ll)(x+y));
for(int i=1;i<=n;i++){
for(auto j:adj2[i]){
for(int k=0;k<2;k++){
pref[i][k].pb(dist[i][j.f][k][0]+e[j.s].f);
suf[i][k].pb(dist[i][j.f][k][0]+e[j.s].f);
}
}
for(int k=0;k<2;k++){
for(int j=1;j<adj2[i].size();j++)pref[i][k][j]=min(pref[i][k][j-1],pref[i][k][j]);
for(int j=adj2[i].size()-2;j>=0;j--)suf[i][k][j]=min(suf[i][k][j+1],suf[i][k][j]);
}
int bruh=0;
for(auto j:adj2[i]){
ans=min(ans,cost[j.s]+get(1,n,i,j.f,e[j.s].f,bruh)+get(n,1,i,j.f,e[j.s].f,bruh));
bruh++;
}
}
if(ans==inf)cout<<-1<<'\n';
else cout<<ans<<'\n';
}
