#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];
ll cost[MAXN];
ll revc[MAXN];
pair<vector<ll>,vector<ll>> dijkstra(ll nd){
vector<ll> dist(n,-1);
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]!=-1) continue;
dist[nd]=c;
pa[nd]=p;
for(auto i:adj[nd]) if(i.snd>=0){
pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
}
}
return {dist,pa};
}
vector<ll> d1N;
vector<ll> p1N;
vector<ll> dN1;
vector<ll> pN1;
pair<ll,ll> ari[MAXM];
ll uind[MAXM];
ll vind[MAXM];
bool principal[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){
principal[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){
principal[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});
cin>>cost[i];
cin>>revc[i];
}
d1N = dijkstra(0).fst;
p1N = dijkstra(0).snd;
dN1 = dijkstra(n-1).fst;
pN1 = dijkstra(n-1).snd;
calcprincipal();
ll res = -1;
if(d1N[n-1]!=-1 && dN1[0]!=-1) res=d1N[n-1]+dN1[0];
forn(i,0,n){
for(auto j:adj[i]) debug(i<<"->"<<j.fst<<" "<<j.snd<<'\n');
}
forn(i,1,m+1){
if(principal[i]||true){
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).fst;
vector<ll> auxN1 = dijkstra(n-1).fst;
debug("dbg "<<aux1N[n-1]<<" "<<auxN1[0]<<'\n');
if(aux1N[n-1]!=-1 && auxN1[0]!=-1) cost+=aux1N[n-1]+auxN1[0];
else cost+=INF;
adj[ari[i].fst][uind[i]].snd*=-1;
adj[ari[i].snd][vind[i]].snd*=-1;
if((res==-1 || res>cost)&&cost<INF) res=cost;
}
}
cout<<res<<'\n';
return 0;
}
