#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Arete
{
int from, to, cost, costFlip;
};
const int MAXN = 200;
const int INF = 1e18;
vector<int> adj[MAXN];
vector<int> adjRev[MAXN];
vector<Arete> aretes;
int nbSommets, nbAretes;
pair<vector<int>, vector<int>> dijsktra(int from, bool flip=false)
{
priority_queue<pair<int, int>> pq;
pq.push({0, from});
vector<int> distance(nbSommets, INF);
vector<int> pred(nbSommets, -1);
distance[from] = 0;
while (!pq.empty())
{
auto [curDis, iNoeud] = pq.top(); pq.pop();
curDis = -curDis;
if (curDis > distance[iNoeud])
continue;
for (auto iArete : (flip ? adjRev[iNoeud] : adj[iNoeud]))
{
int iFrere = flip ? aretes[iArete].from : aretes[iArete].to;
int nxtDis = curDis + aretes[iArete].cost;
if (nxtDis < distance[iFrere])
{
pq.push({-nxtDis, iFrere});
pred[iFrere] = iArete;
distance[iFrere] = nxtDis;
}
}
}
return make_pair(distance, pred);
}
signed main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> nbSommets >> nbAretes;
aretes.resize(nbAretes);
for (auto &[from, to, cost, costFlip] : aretes)
{
cin >> from >> to >> cost >> costFlip;
--from, --to;
}
for (int iArete = 0; iArete < nbAretes; ++iArete)
{
adj[aretes[iArete].from].push_back(iArete);
adjRev[aretes[iArete].to].push_back(iArete);
}
auto [distances0, pred0] = dijsktra(0);
auto [distances0Rev, pred0Rev] = dijsktra(0, 1);
auto [distances1Rev, pred1Rev] = dijsktra(nbSommets-1, 1);
auto [distances1, pred1] = dijsktra(nbSommets-1);
/*for (auto v : distances0)
cout << (v==INF?-1:v) << ' ';
cout << endl;
for (auto v : distances0Rev)
cout << (v==INF?-1:v) << ' ';
cout << endl;
for (auto v : distances1)
cout << (v==INF?-1:v) << ' ';
cout << endl;
for (auto v : distances1Rev)
cout << (v==INF?-1:v) << ' ';
cout << endl;*/
int curSol = distances0[nbSommets-1] + distances1[0];
curSol = min(curSol, INF);
vector<bool> aretesPrise(nbAretes);
if (distances0[nbSommets-1] != INF)
{
int cur = nbSommets-1;
while (cur)
{
assert(pred0[cur] != -1);
aretesPrise[pred0[cur]] = true;
cur = aretes[pred0[cur]].from;
}
}
if (distances1[0] != INF)
{
int cur = 0;
while (cur != nbSommets-1)
{
assert(pred1[cur] != -1);
aretesPrise[pred1[cur]] = true;
cur = aretes[pred1[cur]].from;
}
}
for (int iArete = 0; iArete < nbAretes; ++iArete)
if (!aretesPrise[iArete])
{
int dis0 = min(distances0[nbSommets-1],
distances0[aretes[iArete].to] + distances1Rev[aretes[iArete].from]
+ aretes[iArete].cost);
int dis1 = min(distances1[0],
distances1[aretes[iArete].to] + distances0Rev[aretes[iArete].from]
+ aretes[iArete].cost);
curSol = min(curSol, dis0 + dis1 + aretes[iArete].costFlip);
}
for (int iArete = 0; iArete < nbAretes; ++iArete)
if (aretesPrise[iArete])
{
int iFrom = aretes[iArete].from;
int iTo = aretes[iArete].to;
int posFrom = lower_bound(adj[iFrom].begin(), adj[iFrom].end(), iArete)
- adj[iFrom].begin();
int posTo = lower_bound(adjRev[iTo].begin(), adjRev[iTo].end(), iArete)
- adjRev[iTo].begin();
swap(aretes[iArete].from, aretes[iArete].to);
swap(adj[iFrom][posFrom], adj[iFrom].back());
swap(adjRev[iTo][posTo], adj[iTo].back());
adj[iFrom].pop_back();
adjRev[iTo].pop_back();
adjRev[iFrom].push_back(iArete);
adj[iTo].push_back(iArete);
auto [dis0, p0] = dijsktra(0);
auto [dis1, p1]= dijsktra(nbSommets-1);
curSol = min(curSol, dis0[nbSommets-1] + dis1[0] + aretes[iArete].costFlip);
adj[iTo].pop_back();
adjRev[iFrom].pop_back();
adj[iFrom].push_back(iArete);
adjRev[iTo].push_back(iArete);
swap(adj[iFrom][posFrom], adj[iFrom].back());
swap(adjRev[iTo][posTo], adj[iTo].back());
swap(aretes[iArete].from, aretes[iArete].to);
}
if (curSol == INF)
curSol = -1;
cout << curSol << endl;
}
