#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
#ifdef D
#define debug(x) cout << x
#else
#define debug(x) //nothing
#endif
const int MAXN = 200+5;
const int MAXM = 50000+5;
#define INF ((ll)20000000000000)
ll n,m;
vector<pair<ll,ll>> adj[MAXN];
vector<pair<ll,ll>> radj[MAXN];
ll cost[MAXM];
ll revc[MAXM];
pair<vector<ll>,vector<ll>> dijkstra(ll nd, ll t){
vector<ll> dist(n,INF);
vector<ll> pa(n,-1);
priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}});
while(!pq.empty()){
ll nd = pq.top().snd.fst;
ll c = pq.top().fst*-1;
ll p = pq.top().snd.snd;
pq.pop();
if(dist[nd]<INF) continue;
dist[nd]=c;
pa[nd]=p;
if(t==1){
for(auto i:adj[nd]) if(i.snd>=0){
pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
}
}else{
for(auto i:radj[nd]) if(i.snd>=0){
pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
}
}
}
return {dist,pa};
}
vector<ll> rd1N;
vector<ll> rdN1;
vector<ll> d1N;
vector<ll> p1N;
vector<ll> dN1;
vector<ll> pN1;
pair<ll,ll> ari[MAXM];
ll uind[MAXM];
ll vind[MAXM];
bool princ1N[MAXM];
bool princN1[MAXM];
void calcprincipal(){
ll nd = n-1;
while(p1N[nd]!=-1){
forn(j,0,SZ(adj[p1N[nd]])){
if(adj[p1N[nd]][j].fst==nd){
princ1N[adj[p1N[nd]][j].snd]=true;
}
}
nd=p1N[nd];
}
nd = 0;
while(pN1[nd]!=-1){
forn(j,0,SZ(adj[pN1[nd]])){
if(adj[pN1[nd]][j].fst==nd){
princN1[adj[pN1[nd]][j].snd]=true;
}
}
nd=pN1[nd];
}
}
int main(){
cin>>n>>m;
ll u,v;
forn(i,1,m+1){
cin>>u>>v; u--; v--;
uind[i]=SZ(adj[u]);
vind[i]=SZ(adj[v]);
adj[u].pb({v,i}); ari[i]={u,v};
adj[v].pb({u,-i});
radj[v].pb({u,i});
radj[u].pb({v,-i});
cin>>cost[i];
cin>>revc[i];
}
//cout<<"se llega\n";
d1N = dijkstra(0,1).fst;
p1N = dijkstra(0,1).snd;
dN1 = dijkstra(n-1,1).fst;
pN1 = dijkstra(n-1,1).snd;
//cout<<"se llega\n";
rd1N = dijkstra(0,0).fst;
rdN1 = dijkstra(n-1,0).fst;
//cout<<"se llega\n";
calcprincipal();
//cout<<"se llega\n";
ll b1N = d1N[n-1];
ll bN1 = dN1[0];
ll res = INF;
res=min(res,d1N[n-1]+dN1[0]);
/*cout<<d1N[n-1]<<" "<<dN1[0]<<'\n';
cout<<res<<'\n';*/
forn(i,0,n){
for(auto j:adj[i]) debug(i<<"->"<<j.fst<<" "<<j.snd<<'\n');
}
forn(i,1,m+1){
ll pb1N=b1N;
ll pbN1=bN1;
if(princ1N[i]){
pb1N=INF;
ll cost = revc[i];
adj[ari[i].fst][uind[i]].snd*=-1;
adj[ari[i].snd][vind[i]].snd*=-1;
vector<ll> aux1N = dijkstra(0,1).fst;
cost+=aux1N[n-1];
adj[ari[i].fst][uind[i]].snd*=-1;
adj[ari[i].snd][vind[i]].snd*=-1;
pb1N=min(pb1N,cost);
}else{
//cout<<"-1\n";
pb1N=min(pb1N,revc[i]+rdN1[ari[i].fst]+d1N[ari[i].snd]+cost[i]);
}
if(princN1[i]){
pbN1=INF;
ll cost = revc[i];
adj[ari[i].fst][uind[i]].snd*=-1;
adj[ari[i].snd][vind[i]].snd*=-1;
vector<ll> auxN1 = dijkstra(n-1,1).fst;
cost+=auxN1[0];
adj[ari[i].fst][uind[i]].snd*=-1;
adj[ari[i].snd][vind[i]].snd*=-1;
pbN1=min(pbN1,cost);
}else{
//cout<<"-2\n";
pbN1=min(pbN1,revc[i]+rd1N[ari[i].fst]+dN1[ari[i].snd]+cost[i]);
}
//cout<<"dando vuelta "<<i<<" "<<pb1N<<" "<<pbN1<<'\n';
res=min(res, pb1N+pbN1);
}
if(res>=INF) res=-1;
cout<<res<<'\n';
return 0;
}
