#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int inf = 1e18,mxn = 2e3+5;
int u[mxn*100],v[mxn*100],w[mxn*100],c[mxn*100],ok[mxn*100],anne[mxn];
int d[mxn][mxn];
vector<int> a[mxn];
void bul(int i)
{
vector<int> dist(n+1,inf);
dist[i] = 0;
for(int i=1;i<=n;i++) anne[i] = -1;
priority_queue<array<int,2>> pq;
pq.push({0,1});
while(pq.size())
{
int s = pq.top()[1];
pq.pop();
for(int x:a[s])
{
if(dist[v[x]]>dist[s]+w[x])
{
anne[v[x]] = x;
dist[v[x]] = dist[s]+w[x];
pq.push({-dist[v[x]],v[x]});
}
}
}
for(int i=1;i<=n;i++)
{
if(anne[i]!=-1)
{
ok[anne[i]] = 1;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i=1;i<=n;i++)
{
anne[i] = -1;
for(int j = 1;j<=n;j++)
{
d[i][j]=inf;
}
d[i][i] = 0;
}
for(int i=0;i<m;i++)
{
ok[i] = 0;
cin >> u[i]>> v[i]>> w[i]>> c[i];
d[u[i]][v[i]] = min(d[u[i]][v[i]],w[i]);
a[u[i]].push_back(i);
}
for(int k = 0;k<n;k++)
{
for(int u = 0;u<n;u++)
{
for(int v = 0;v<n;v++)
{
u++;
v++;
k++;
d[u][v] = min(d[u][v],d[u][k]+d[k][v]);
u--;
v--;
k--;
}
}
}
// bul(1);
// bul(n);
int b = d[1][n],s = d[n][1];
int ans = b+s;
/// cout << ans << endl;
for(int i=0;i<m;i++)
{
if(ok[i]) continue;
int mn = min(b,d[1][v[i]]+w[i]+d[u[i]][n]);
int sn = min(s,d[n][v[i]]+w[i]+d[u[i]][1]);
ans = min(ans,mn+sn+c[i]);
}
if(ans>=inf) ans = -1;
cout << ans << endl;
}
