#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e2+10, maxm=5e4+10, lg=21, mod=1e9+7, inf=1e18;
ll n,m,V[maxm],U[maxm],C[maxm],ans[maxm];
bool mk[maxn];
void dij(ll sr,vector<ll> adj[],ll dis[],ll par[]){
for(int i=0;i<=n;i++) dis[i]=inf, par[i]=mk[i]=0;
dis[sr]=0;
while(1){
ll v=0;
for(int i=1;i<=n;i++)if(!mk[i] && dis[i]<dis[v]) v=i;
if(!v) return;
mk[v]=1;
for(auto i:adj[v]){
ll u=V[i]^U[i]^v;
if(dis[v]+C[i]<dis[u]) dis[u]=dis[v]+C[par[u]=i];
}
}
}
ll dis[3][maxn],py[3][maxn];
vector<ll> g[maxn],rg[maxn],gg[maxn];
bool dd[maxm];
void solve(ll a,ll b){
dij(a,g,dis[0],py[0]), dij(b,rg,dis[1],py[1]);
ans[0]+=dis[0][b];
memset(dd,0,sizeof(dd)); for(int i=1;i<=n;i++) dd[py[0][i]]=dd[py[1][i]]=1;
for(int i=1;i<=m;i++){
if(dis[0][U[i]]>=inf || dis[1][V[i]]>=inf){
ans[i]+=inf;
continue;
}
if(!dd[i]) ans[i]+=min(dis[0][b],dis[0][U[i]]+C[i]+dis[1][V[i]]);
else{
for(int i=1;i<=n;i++) gg[i].clear();
for(int j=1;j<=m;j++)if(i!=j) gg[V[j]].pb(j);
gg[U[i]].pb(i);
dij(a,gg,dis[2],py[2]);
ans[i]+=dis[2][b];
}
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//memset(ans,69,sizeof(ans));
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>V[i]>>U[i]>>C[i]>>ans[i];
g[V[i]].pb(i), rg[U[i]].pb(i);
}
solve(1,n), solve(n,1);
ll jj=inf;
for(int i=0;i<=m;i++) jj=min(jj,ans[i]);
cout<<(jj>=inf ? -1:jj);
return 0;
}
