#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});
}
}
}
int get(int x,int y,int a,int b,int c){
//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(E[b][a].size()){
int k=(E[b][a][0]==c);
if(E[b][a].size()>k){
ans=min(ans,(ll)(dist[a][b][(x==n)][0]+dist[b][a][(y==n)][1]+E[b][a][k]));
}
}
//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];
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));
int c=0;
for(auto i:e){
ans=min(ans,(ll)(cost[c]+get(1,n,i.s.s,i.s.f,i.f)+get(n,1,i.s.s,i.s.f,i.f)));
c++;
}
if(ans==inf)cout<<-1<<'\n';
else cout<<ans<<'\n';
}
