#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll infl = 1e18;
ll ans;
vector<vector<vector<ll>>> gr;
ll co[200][2];
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pq;
void dk(int p,ll c,int t)
{
//cout<<p<<" "<<c<<" "<<t<<"\n";
for(int i = 0;i<gr[p].size();i++)
{
/*if(p == 2 && t == 1)
{
cout<<gr[p][i][0]<<" "<<gr[p][i][1]<<"\n";
}*/
if(co[gr[p][i][0]][t] > c + gr[p][i][1])
{
co[gr[p][i][0]][t] = c + gr[p][i][1];
pq.push({c + gr[p][i][1],gr[p][i][0],t});
}
}
}
int main()
{
int n,m;
cin>>n>>m;
gr.resize(n);
for(int i =0 ;i<m;i++)
{
int u,v,c,d;
cin>>u>>v>>c>>d;
u--;v--;
gr[u].push_back({v,c,d});
}
ll tans = infl;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<gr[i].size();j++)
{
vector<ll> cu = gr[i][j];
gr[i][j][1] = infl;
gr[gr[i][j][0]].push_back({i,cu[1],cu[2] });
ans = gr[i][j][2];
pq.push({0,0,0});
pq.push({0,n-1,1});
for(int q = 0;q<n;q++)
{
co[q][0] = infl;
co[q][1] = infl;
}
co[0][0] = 0;
co[n-1][1] = 0;
while(!pq.empty())
{
ll b =pq.top()[0];
int a = pq.top()[1];
int t = pq.top()[2];
pq.pop();
if(b == co[a][t]) dk(a,b,t);
}
//cout<<co[n-1][0]<<" "<<co[0][1]<<"\n";
ans+= co[n-1][0];
ans += co[0][1];
tans = min(tans,ans);
gr[cu[0]].pop_back();
gr[i][j][1] = cu[1];
}
}
ans = 0;
pq.push({0,0,0});
pq.push({0,n-1 ,1});
for(int q = 0;q<n;q++)
{
co[q][0] = infl;
co[q][1] = infl;
}
co[0][0] = 0;
co[n-1][1] = 0;
while(!pq.empty())
{
ll b =pq.top()[0];
int a = pq.top()[1];
int t = pq.top()[2];
pq.pop();
if(b == co[a][t]) dk(a,b,t);
}
ans+= co[n-1][0];
ans += co[0][1];
//cout<<co[n-1][0]<<" "<<co[0][1]<<"\n";
tans = min(tans,ans);
if(tans >= 1e18)
{
cout<<-1;
}
else
{
cout<<tans;
}
}
