#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll
int n,m;
pair<pair<int,int>,pair<int,int>>ed[50023];
vector<pair<ll,int>>git1,gel1,gitn,geln;
vector<int>h[223][223],o[223][223];
vector<pair<ll,int>> f(int bas,bool t){
vector<bool>vis(n,false);
vector<pair<ll,int>>dp(n,{2e15,2e15});
dp[bas]={0,0};
while(true){
int pos=-1;
for(int i=0;i<n;i++){
if(vis[i])continue;
if(pos==-1||dp[i].fr<dp[pos].fr)pos=i;
}
if(pos==-1)break;
vis[pos]=true;
for(int i=0;i<n;i++){
if(vis[i])continue;
vector<int>&v=(t?o:h)[pos][i];
if(!v.size())continue;
dp[i]=min(dp[i],{dp[pos].fr+ed[v.back()].sc.fr,v.back()});
}
}
return dp;
}
int32_t main(){
ios_base::sync_with_stdio(23^23);cin.tie(NULL);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c,d;cin>>a>>b>>c>>d;
a--;b--;
ed[i]={{a,b},{c,d}};
h[a][b].pb(i);
o[b][a].pb(i);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sort(h[i][j].begin(),h[i][j].end(),[&](const int &x,const int &y){
return ed[x].sc.fr>ed[y].sc.fr;
});
sort(o[i][j].begin(),o[i][j].end(),[&](const int &x,const int &y){
return ed[x].sc.fr>ed[y].sc.fr;
});
}
}
git1=f(0,0);
gel1=f(0,1);
gitn=f(n-1,0);
geln=f(n-1,1);
ll ans=git1[n-1].fr+gitn[0].fr;
for(int i=1;i<=m;i++){
int a=ed[i].fr.fr,b=ed[i].fr.sc,c=ed[i].sc.fr,d=ed[i].sc.sc;
ll res=d;
if(git1[b].sc!=i&&geln[a].sc!=i){
res+=min(git1[n-1].fr,git1[b].fr+geln[a].fr+c);
}
else{
int x=0;
if(h[a][b].back()==i){
h[a][b].pop_back();
o[b][a].pop_back();
x+=1;
}
if(h[b][a].size()==0||ed[h[b][a].back()].sc.fr>c){
h[b][a].pb(i);
o[a][b].pb(i);
x+=2;
}
res+=f(0,0)[n-1].fr;
if(x&2){
h[b][a].pop_back();
o[a][b].pop_back();
}
if(x&1){
h[a][b].pb(i);
o[b][a].pb(i);
}
}
if(gitn[b].sc!=i&&gel1[a].sc!=i){
res+=min(gitn[0].fr,gitn[b].fr+gel1[a].fr+c);
}
else{
int x=0;
if(h[a][b].back()==i){
h[a][b].pop_back();
o[b][a].pop_back();
x+=1;
}
if(h[b][a].size()==0||ed[h[b][a].back()].sc.fr>c){
h[b][a].pb(i);
o[a][b].pb(i);
x+=2;
}
res+=f(n-1,0)[0].fr;
if(x&2){
h[b][a].pop_back();
o[a][b].pop_back();
}
if(x&1){
h[a][b].pb(i);
o[b][a].pb(i);
}
}
ans=min(ans,res);
}
if(ans>=2e15){
cout<<-1<<endl;
}
else cout<<ans<<endl;
}
