#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=205, mx=5e4+5;
ll n, m, u[mx], v[mx], s[mx], rs[mx], c[mx], f[mx],vs[nx], cur, res=1e18;
vector<vector<pair<ll, ll>>> d(nx), rv(nx);
vector<ll> st(nx), ed(nx), rst(nx), red(nx), tmp1(nx), tmp2(nx);
vector<pair<ll, ll>> b(nx), rb(nx), h(nx);
void dijkstra(ll rt, vector<ll> &mn, vector<vector<pair<ll, ll>>> &g, ll ban, vector<pair<ll, ll>> &bk)
{
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
for (int i=1; i<=n ;i++) mn[i]=1e18, vs[i]=0;
mn[rt]=0;
bk[rt]={-1, -1};
pq.push({0, rt});
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto [v, idx]:g[u])
{
if (idx==ban) continue;
if (mn[v]>cw+c[idx]) bk[v]={u, idx}, mn[v]=cw+c[idx], pq.push({mn[v], v});
}
}
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>u[i]>>v[i]>>c[i]>>f[i], d[u[i]].push_back({v[i], i}), rv[v[i]].push_back({u[i], i});
dijkstra(1, st, d, -1, b);
dijkstra(n, ed, d, -1, rb);
dijkstra(1, rst, rv, -1, h);
dijkstra(n, red, rv, -1, h);
if (st[n]!=1e18)
{
cur=n;
while (b[cur].second!=-1) s[b[cur].second]=1, cur=b[cur].first;
}
if (ed[1]!=1e18)
{
cur=1;
while (rb[cur].second!=-1) rs[rb[cur].second]=1, cur=rb[cur].first;
}
res=min(res, st[n]+ed[1]);
for (int i=1; i<=m; i++)
{
if (s[i]||rs[i])
{
c[m+1]=c[i];
d[v[i]].push_back({u[i], m+1});
dijkstra(1, tmp1, d, i, h);
dijkstra(n, tmp2, d, i, h);
d[v[i]].pop_back();
res=min(res, tmp1[n]+tmp2[1]+f[i]);
}
else
{
res=min(res, min(st[n], st[v[i]]+c[i]+red[u[i]])+min(ed[1], ed[v[i]]+c[i]+rst[u[i]])+f[i]);
}
//cout<<"res "<<i<<' '<<res<<'\n';
}
if (res==1e18) cout<<-1;
else cout<<res;
}
/*
2 2
1 2 3 3
1 2 3 3
4 5
1 2 1 1
3 2 1 1
3 4 1 1
4 2 1 1
3 1 1 1
*/
