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