#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 5e4+5;
const ll INF = 1e18;
#define sz(a) (int)(a.size())
ll c[MAXN],d[MAXN],dist[MAXN];
int n,m;
array<int,2>par[201];
vector<array<int,2>>g[201],gr[201];
bool block[MAXN],vis[201];
void djikstra(int v,vector<array<int,2>>*g){
for(int i=1;i<=n;i++)dist[i] = INF,vis[i] = 0;
dist[v] = 0;
while(true){
int u = 0;
for(int i=1;i<=n;i++)if(dist[i] < dist[u] && !vis[i])u = i;
if(!u)break;
vis[u] = 1;
for(auto x:g[u]){
if(block[x[1]])continue;
if(dist[u] + c[x[1]] < dist[x[0]]){
dist[x[0]] = dist[u] + c[x[1]];
par[x[0]] = {u,x[1]};
}
}
}
}
vector<int>path;
ll notused[2][201],used[2][201];
int main()
{
cin>>n>>m;
ll thonk = 0;
dist[0] = INF;
vector<array<int,2>>edge;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u>>c[i]>>d[i];
g[v].push_back({u,i});
gr[u].push_back({v,i});
edge.push_back({v,u});
}
djikstra(1,g);
thonk+=dist[n];
for(int i=0;i<m;i++)used[0][i]+=dist[edge[i][1]] + c[i];
for(int i=0;i<m;i++)notused[0][i] = dist[n];
if(dist[n] != INF){
int cur = n;
while(cur!=1){
path.push_back(par[cur][1]);
cur = par[cur][0];
}
for(int x:path){
block[x] = 1;
djikstra(1,g);
used[0][x] = dist[n];
block[x] = 0;
}
}
djikstra(n,gr);
for(int i=0;i<m;i++)used[0][i]+=dist[edge[i][0]];
djikstra(n,g);
thonk+=dist[1];
for(int i=0;i<m;i++)used[1][i]+=dist[edge[i][1]] + c[i];
for(int i=0;i<m;i++)notused[1][i] = dist[1];
if(dist[1] != INF){
int cur = n;
while(cur!=1){
path.push_back(par[cur][1]);
cur = par[cur][0];
}
for(int x:path){
block[x] = 1;
djikstra(n,g);
used[1][x] = dist[1];
block[x] = 0;
}
}
djikstra(1,gr);
for(int i=0;i<m;i++)used[1][i]+=dist[edge[i][0]];
ll ans = min(INF,thonk);
for(int i=0;i<m;i++){
ans = min(ans,min(used[0][i],notused[0][i]) + min(used[1][i],notused[1][i]) + d[i]);
}
if(ans == INF)ans = -1;
cout<<ans;
}
