#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];
int matAdj[MAXN][MAXN];
vector<Arete> aretes;
int nbSommets, nbAretes;
// O(M log N)
pair<vector<int>, vector<int>> dijsktra(int from, bool flip=false)
{
priority_queue<pair<int, int>> pq;
pq.push({0, from});
vector<int> distances, pred;
distances.assign(nbSommets, INF);
pred.assign(nbSommets, -1);
distances[from] = 0;
while (!pq.empty())
{
auto [curDis, iNoeud] = pq.top(); pq.pop();
curDis = -curDis;
if (curDis > distances[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 < distances[iFrere])
{
pq.push({-nxtDis, iFrere});
pred[iFrere] = iArete;
distances[iFrere] = nxtDis;
}
}
}
return make_pair(move(distances), move(pred));
}
int disjk(int from, int to)
{
priority_queue<pair<int, int>> pq;
pq.push({0, from});
vector<int> dis(nbSommets, INF);
dis[from] = 0;
while (!pq.empty())
{
auto [curDis, iNoeud] = pq.top(); pq.pop();
curDis = -curDis;
if (curDis > dis[iNoeud]) continue;
if (iNoeud == to) return curDis;
for (int iFrere(0); iFrere < nbSommets; ++iFrere)
if (curDis + matAdj[iNoeud][iFrere] < dis[iFrere])
{
dis[iFrere] = curDis + matAdj[iNoeud][iFrere];
pq.push({-dis[iFrere], iFrere});
}
}
return INF;
}
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 [distances1, pred1] = dijsktra(nbSommets-1);
auto [distances1Rev, pred1Rev] = dijsktra(nbSommets-1, 1);
int curSol = INF;
if (distances0[nbSommets-1] < INF and distances1[0] < INF)
curSol = distances0[nbSommets-1] + distances1[0];
vector<bool> aretesPrise(nbAretes);
if (distances0[nbSommets-1] != INF)
{
int cur = nbSommets-1;
while (cur)
{
aretesPrise[pred0[cur]] = true;
cur = aretes[pred0[cur]].from;
}
}
if (distances1[0] != INF)
{
int cur = 0;
while (cur != nbSommets-1)
{
aretesPrise[pred1[cur]] = true;
cur = aretes[pred1[cur]].from;
}
}
// O(NM log N)
for (int iArete = 0; iArete < nbAretes; ++iArete)
if (!aretesPrise[iArete])
{
int dis0 = distances0[nbSommets-1];
int dis1 = distances1[0];;
int iTo = aretes[iArete].to;
int iFrom = aretes[iArete].from;
if (distances0[iTo] < INF and distances1Rev[iFrom] < INF)
dis0 = min(dis0,
distances0[aretes[iArete].to] + distances1Rev[aretes[iArete].from]
+ aretes[iArete].cost);
if (distances1[iTo] < INF and distances0Rev[iFrom] < INF)
dis1 = min(dis1,
distances1[aretes[iArete].to] + distances0Rev[aretes[iArete].from]
+ aretes[iArete].cost);
if (dis0 < INF and dis1 < INF)
curSol = min(curSol, dis0 + dis1 + aretes[iArete].costFlip);
}
// If we
for (int iArete = 0; iArete < nbAretes; ++iArete)
if (aretesPrise[iArete])
{
for (int i = 0; i < nbSommets; ++i)
for (int j = 0; j < nbSommets; ++j)
matAdj[i][j] = INF;
for (int iArete2 = 0; iArete2 < nbAretes; ++iArete2)
{
int u = aretes[iArete2].from;
int v = aretes[iArete2].to;
if (iArete2 == iArete)
swap(u, v);
matAdj[u][v] = min(matAdj[u][v], aretes[iArete2].cost);
}
curSol = min(curSol, aretes[iArete].costFlip + disjk(0, nbSommets-1) + disjk(nbSommets-1, 0));
}
if (curSol == INF)
curSol = -1;
cout << curSol << endl;
}
