#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int MOD=1e9+7,N=203;
struct Edge {
int u,v,w,d;
};
int n,m;
ll f[N][N],f1[N][N];
Edge e[50003];
bool c[50003],vs[N];
vector<int> g[N],tp;
ll ans[50003],dp1[N],dp2[N];
void dfs(int u) {
for(auto i: g[u])
if (!vs[e[i].v]) {
vs[e[i].v]=1;
dfs(e[i].v);
}
tp.pb(u);
}
void solve(int s,int t) {
For(i,1,n) g[i].clear();
fill(c+1,c+1+m,0);
fill(vs+1,vs+1+n,0);
For(i,1,m)
if (f[s][e[i].u]+f[e[i].v][t]+e[i].w==f[s][t]) g[e[i].u].pb(i);
tp.clear();
For(i,1,n)
if (!vs[i]) dfs(i);
fill(dp1,dp1+1+n,0);
fill(dp2,dp2+1+n,0);
dp1[s]=1;
dp2[t]=1;
reverse(all(tp));
for(auto u: tp)
for(auto i: g[u]) {
int v=e[i].v;
dp1[v]=(dp1[v]+dp1[u])%MOD;
}
ForD(j,sz(tp)-1,0) {
int u=tp[j];
for(auto i: g[u]) {
int v=e[i].v;
dp2[u]=(dp2[u]+dp2[v])%MOD;
}
}
For(i,1,n)
for(auto el: g[i]) {
int u=e[el].u,v=e[el].v;
ll kk=1LL*dp1[u]*dp2[v]%MOD;
kk=(kk-dp1[t])%MOD;
if (kk==0) c[el]=1;
}
For(i,1,n) {
For(j,1,n)
f1[i][j]=1e17;
f1[i][i]=0;
}
For(i,1,m)
if (!c[i]) f1[e[i].u][e[i].v]=min(f1[e[i].u][e[i].v],(ll)e[i].w);
For(k,1,n)
For(i,1,n)
For(j,1,n) f1[i][j]=min(f1[i][j],f1[i][k]+f1[k][j]);
For(i,1,m) {
ll tmp=1e18;
int u=e[i].u,v=e[i].v,w=e[i].w;
if (f[s][u]>=f[s][v]) {
tmp=f[s][v]+w+f[u][t];
// debug(i,tmp);
}
if (c[i]) {
For(j,1,n)
For(k,1,n) {
if (f[s][u]+f[v][j]+w!=f[s][j] && f[k][u]+w+f[v][t]!=f[k][t])
tmp=min(tmp,f[s][j]+f[k][t]+f1[j][k]);
}
} else tmp=min(tmp,f[s][t]);
ans[i]+=tmp;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
For(i,1,m) {
cin >> e[i].u >> e[i].v >> e[i].w >> e[i].d;
}
For(i,1,n) {
For(j,1,n)
f[i][j]=f1[i][j]=1e17;
f[i][i]=f1[i][i]=0;
}
For(i,1,m) f[e[i].u][e[i].v]=min(f[e[i].u][e[i].v],(ll)e[i].w);
For(k,1,n)
For(i,1,n)
For(j,1,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
ll res=1e18;
solve(1,n);
solve(n,1);
For(i,1,m)
res=min(res,ans[i]+e[i].d);
res=min(res,f[1][n]+f[n][1]);
if (res>=1e16) cout << -1 << endl;
else cout << res << endl;
return 0;
}
