#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 200;
const int MAXM = 5e4;
const ll INF = 1e18;
struct Edge
{
int u, v; ll c, d; int p;
bool operator < (const Edge &q) const { return p<q.p; }
};
int N, M;
vector<Edge> adj[MAXN+10], radj[MAXN+10];
Edge E[MAXM+10];
ll ans[MAXM+10];
ll DA[MAXN+10], DB[MAXN+10], RDA[MAXN+10], RDB[MAXN+10];
int PA[MAXN+10], PB[MAXN+10], RPA[MAXN+10], RPB[MAXN+10];
ll TD[MAXN+10];
int TP[MAXN+10];
bool vis[MAXN+10];
void dijk(vector<Edge> *G, int S, ll *D, int *P)
{
for(int i=1; i<=N; i++) D[i]=INF, P[i]=-1, vis[i]=0;
D[S]=0;
while(1)
{
int now=-1; ll val=INF;
for(int i=1; i<=N; i++)
{
if(vis[i]) continue;
if(val>D[i]) val=D[i], now=i;
}
if(now==-1) break;
vis[now]=1;
//printf("!%d %lld\n", now, val);
for(auto nxt : G[now])
{
if(vis[nxt.v]) continue;
if(val+nxt.c<=D[nxt.v])
{
D[nxt.v]=val+nxt.c;
P[nxt.v]=nxt.p;
}
}
}
}
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++)
{
int u, v, c, d;
scanf("%d%d%d%d", &u, &v, &c, &d);
adj[u].push_back({u, v, c, d, i});
radj[v].push_back({v, u, c, d, i});
E[i]={u, v, c, d, i};
}
for(int i=1; i<=N; i++) sort(adj[i].begin(), adj[i].end());
dijk(adj, 1, DA, PA);
dijk(adj, N, DB, PB);
dijk(radj, 1, RDA, RPA);
dijk(radj, N, RDB, RPB);
{
vector<int> V;
for(int i=1; i<=N; i++) if(PA[i]) V.push_back(PA[i]);
for(int i=1; i<=N; i++) if(RPB[i]) V.push_back(RPB[i]);
sort(V.begin(), V.end());
for(int i=1; i<=M; i++)
{
if(binary_search(V.begin(), V.end(), i))
{
auto it=lower_bound(adj[E[i].u].begin(), adj[E[i].u].end(), E[i]);
it->c=INF;
dijk(adj, 1, TD, TP);
ans[i]+=TD[N];
it->c=E[i].c;
}
else
{
ans[i]+=min(DA[E[i].v]+E[i].c+RDB[E[i].u], DA[N]);
}
}
}
{
vector<int> V;
for(int i=1; i<=N; i++) if(PB[i]) V.push_back(PB[i]);
for(int i=1; i<=N; i++) if(RPA[i]) V.push_back(RPA[i]);
sort(V.begin(), V.end());
for(int i=1; i<=M; i++)
{
if(binary_search(V.begin(), V.end(), i))
{
auto it=lower_bound(adj[E[i].u].begin(), adj[E[i].u].end(), E[i]);
it->c=INF;
dijk(adj, N, TD, TP);
ans[i]+=TD[1];
it->c=E[i].c;
}
else
{
ans[i]+=min(DB[E[i].v]+E[i].c+RDA[E[i].u], DB[1]);
}
}
}
for(int i=1; i<=M; i++) ans[i]+=E[i].d;
ll val=DA[N]+DB[1];
for(int i=1; i<=M; i++) val=min(val, ans[i]);
if(val>=INF) val=-1;
printf("%lld\n", val);
}
