#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=50505;
const ll INF=1e18;
int n,m;
multiset<ii> adj[N];
int uu[N],vv[N],cc[N],dd[N];
ll d[202][202],dist[N];
ll dijkstra(int x, int y){
foru(i,1,n) dist[i]=INF;
priority_queue<ii,vector<ii>,greater<ii>>pq;
dist[x]=0;
pq.push({dist[x],x});
while(pq.size()){
auto [du,u]=pq.top(); pq.pop();
if(du>dist[u]) continue;
for(auto [v,w]:adj[u]){
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pq.push({dist[v],v});
}
}
}
return dist[y];
}
void solve(){
cin>>n>>m;
foru(i,1,n) foru(j,1,n) d[i][j]=INF;
foru(i,1,m){
cin>>uu[i]>>vv[i]>>cc[i]>>dd[i];
mini(d[uu[i]][vv[i]],cc[i]);
adj[uu[i]].insert(ii(vv[i],cc[i]));
}
/// floyd
foru(i,1,n) d[i][i]=0;
foru(k,1,n){
foru(i,1,n) foru(j,1,n){
mini(d[i][j], d[i][k]+d[k][j]);
}
}
ll res=d[1][n]+d[n][1];
foru(i,1,m){
ll go =min(d[1][n],d[1][vv[i]]+cc[i]+d[uu[i]][n]),
ret=min(d[n][1],d[n][vv[i]]+cc[i]+d[uu[i]][1]);
if(go+ret+dd[i]<res){
adj[uu[i]].erase(adj[uu[i]].find(ii(vv[i],cc[i])));
adj[vv[i]].insert(ii(uu[i],cc[i]));
mini(res,dijkstra(1,n)+dijkstra(n,1)+dd[i]);
adj[vv[i]].erase(adj[vv[i]].find(ii(uu[i],cc[i])));
adj[uu[i]].insert(ii(vv[i],cc[i]));
}
}
if(res>=INF) cout<<"-1\n";
else cout<<res<<'\n';
}
int32_t main(){
#define task "test"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin.tie(0)->sync_with_stdio(0);
int tc=1; //cin>>tc;
rep(i,tc){
solve();
}
}
