#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 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)100000000000000)
ll n,m;
struct Ari{
ll i;
ll nd;
ll to;
ll cost;
ll revcost;
ll type;
Ari(ll i=0, ll nd=0, ll to=0 , ll cost=0,ll revcost=0, ll type=0 ):i(i),nd(nd),to(to), cost(cost),revcost(revcost), type(type) {}
};
vector<Ari> adj[MAXN];
vector<Ari> radj[MAXN];
ll myInd[MAXM];
ll rmyInd[MAXM];
Ari ari[MAXM];
Ari revari[MAXM];
struct ResDijkstra{
vector<ll> dis;
vector<ll> myp;
ResDijkstra(vector<ll> dis={}, vector<ll> myp={}):dis(dis),myp(myp){}
};
ResDijkstra dijkstra(ll nd){
vector<ll> dis(n+2,INF);
vector<ll> myp(n+2,INF);
priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}}); dis[nd]=0;
while(!pq.empty()){
ll nd = pq.top().snd.fst;
ll c = pq.top().fst*-1;
ll p = pq.top().snd.snd;
pq.pop();
if(dis[nd]!=c) continue;
debug(nd<<" "<<p<<'\n');
for(auto a:adj[nd]){
if(a.type==-1) continue;
if(a.cost+c<dis[a.to]){
dis[a.to]=a.cost+c;
myp[a.to]=a.i;
pq.push({ (a.cost+c)*-1, {a.to, a.i}});
}
}
}
return ResDijkstra(dis,myp);
}
ResDijkstra revdijkstra(ll nd){
vector<ll> dis(n+2,INF);
vector<ll> myp(n+2,INF);
priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}}); dis[nd]=0;
while(!pq.empty()){
ll nd = pq.top().snd.fst;
ll c = pq.top().fst*-1;
ll p = pq.top().snd.snd;
pq.pop();
if(dis[nd]!=c) continue;
for(auto a:radj[nd]){
if(a.type==-1) continue;
if(a.cost+c<dis[a.to]){
dis[a.to]=a.cost+c;
myp[a.to]=a.i;
pq.push({ (a.cost+c)*-1, {a.to, a.i}});
}
}
}
return ResDijkstra(dis,myp);
}
bool way1toN[MAXM];
bool wayNto1[MAXM];
ll dis1toX[MAXN];
ll disXtoN[MAXN];
ll disXto1[MAXN];
ll disNtoX[MAXN];
ll myp1toX[MAXN];
ll mypNtoX[MAXN];
void recoverWay(){
ll nd = 1;
while(mypNtoX[nd]!=INF){
wayNto1[mypNtoX[nd]]=true;
nd = ari[mypNtoX[nd]].nd;
}
nd = n;
while(myp1toX[nd]!=INF){
way1toN[myp1toX[nd]]=true;
nd = ari[myp1toX[nd]].nd;
}
}
int main(){ FIN;
cin>>n>>m;
forn(i,1,m+1){
cin>>ari[i].nd;
cin>>ari[i].to;
cin>>ari[i].cost;
cin>>ari[i].revcost;
ari[i].type=1;
ari[i].i=i;
myInd[i]=SZ(adj[ari[i].nd]);
adj[ari[i].nd].pb(ari[i]);
Ari rari; // reverse arista
rari.i=i;
rari.nd=ari[i].to;
rari.to=ari[i].nd;
rari.cost=ari[i].cost;
rari.revcost=ari[i].revcost;
rari.type=1;
rmyInd[i]=SZ(adj[rari.nd]);
revari[i]=rari;
radj[rari.nd].pb(rari);
}
debug("Precalculos\n");
{ // precalculos
ResDijkstra aux;
// 1 to X
aux=dijkstra(1);
forn(i,0,SZ(aux.dis)){
dis1toX[i]=aux.dis[i];
myp1toX[i]=aux.myp[i];
}
// N to x
aux=dijkstra(n);
forn(i,0,SZ(aux.dis)){
disNtoX[i]=aux.dis[i];
mypNtoX[i]=aux.myp[i];
}
debug("Fase 1 Lista\n");
//Recuperar los caminos
recoverWay();
debug("Fase 2 Lista\n");
// X to N
aux=revdijkstra(n);
forn(i,0,SZ(aux.dis)){
disXtoN[i]=aux.dis[i];
}
// X to 1
aux=revdijkstra(1);
forn(i,0,SZ(aux.dis)){
disXto1[i]=aux.dis[i];
}
debug("Fase 3 Lista\n");
}
{
// calcular respuesta
ll best1toN = dis1toX[n];
ll bestNto1 = disNtoX[1];
ll res = INF;
res=min(res, best1toN+bestNto1);
forn(i,1,m+1){
ll auxbest1toN = best1toN;
ll auxbestNto1 = bestNto1;
if(way1toN[i]){
auxbest1toN = INF;
adj[ari[i].nd][myInd[i]].type=-1;
adj[ari[i].to].pb(revari[i]);
ResDijkstra aux;
aux=dijkstra(1);
auxbest1toN=min(auxbest1toN,aux.dis[n]);
adj[ari[i].nd][myInd[i]].type=1;
adj[ari[i].to].pop_back();
}else{
auxbest1toN = min( auxbest1toN , dis1toX[ari[i].to] + disXtoN[ari[i].nd] + ari[i].cost );
}
if(wayNto1[i]){
auxbestNto1 = INF;
adj[ari[i].nd][myInd[i]].type=-1;
adj[ari[i].to].pb(revari[i]);
ResDijkstra aux;
aux=dijkstra(n);
auxbestNto1=min(auxbestNto1,aux.dis[1]);
adj[ari[i].nd][myInd[i]].type=1;
adj[ari[i].to].pop_back();
}else{
auxbestNto1 = min( auxbestNto1 , disNtoX[ari[i].to] + disXto1[ari[i].nd] + ari[i].cost );
}
res=min( res , auxbest1toN+auxbestNto1+ari[i].revcost );
}
if(res==INF) res=-1;
cout<<res<<'\n';
}
return 0;
}
