#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],g1[N];
ll ans[50003];
void dfs(int u,int idx) {
vs[u]=1;
for(auto i: g[u]) {
if (i==idx) continue;
int v=e[i].v;
if (!vs[v]) dfs(v,idx);
}
}
void solve(int s,int t) {
For(i,1,n) g[i].clear();
fill(c+1,c+1+m,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);
For(i,1,m)
if (f[s][e[i].u]+f[e[i].v][t]+e[i].w==f[s][t]) {
fill(vs,vs+1+n,0);
dfs(s,i);
c[i]=!(vs[t]);
}
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]);
int sigma=0;
For(i,1,m) sigma+=c[i];
assert(sigma<=n);
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];
}
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;
}
