#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mxn = 2e3+3;
int n;
vector<array<int,2>> a[mxn+1];
int bul(int i,int j)
{
vector<int> dist(n+1,1e18);
dist[i] = 0;
priority_queue<array<int,2>> pq;
pq.push({0,i});
while(pq.size())
{
int s = pq.top()[1];
pq.pop();
for(auto k:a[s])
{
int x = k[0],w = k[1];
if(w==1e18) continue;
if(dist[x]>(dist[s]+w))
{
dist[x] = dist[s]+w;
pq.push({-dist[x],x});
}
}
}
return dist[j];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin >> n >> m;
vector<array<int,4>> nw(m);
for(int i=0;i<m;i++)
{
int u,v,c,d;
cin >> u >> v >> c >> d;
a[u].push_back({v,c});
nw[i] = {u,v,c,d};
}
int ans = min((int)1e18,bul(1,n)+bul(n,1));
for(int i=0;i<m;i++)
{
int u = nw[i][0], v = nw[i][1],c = nw[i][2],d = nw[i][3];
for(int j=0;j<a[u].size();j++)
{
if(a[u][j][0]==v && a[u][j][1]==c)
{
a[u][j][1] = 1e18;
break;
}
}
a[v].push_back({u,c});
ans = min(ans,bul(1,n)+bul(n,1)+d);
a[v].pop_back();
for(int j=0;j<a[u].size();j++)
{
if(a[u][j][0]==v && a[u][j][1]==1e18)
{
a[u][j][1] = c;
break;
}
}
}
if(ans==1e18) cout << -1 << endl;
else cout << ans << endl;
}
