#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = false;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"), cout << flush; }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
const int MAXV = 205;
const int MAXE = 5e4 + 10;
const ll INF = 1e15;
int V, E;
int u[MAXE], v[MAXE];
ll c[MAXE], r[MAXE];
int src;
int sink;
vi aL[MAXV];
ll cost[MAXV];
int pEdge[MAXV];
vi sEdges;
void dijkstra() {
for (int i = 0; i < V; i++) {
aL[i].clear();
}
for (int i = 0; i < E; i++) {
aL[u[i]].pb(i);
}
fill(cost, cost + MAXV, INF);
fill(pEdge, pEdge + MAXV, -1);
sEdges.clear();
priority_queue<pi, vector<pi>, greater<pi>> q;
cost[src] = 0;
q.push({0, src});
while (!q.empty()) {
pi st = q.top();
q.pop();
ll cC = st.f;
int cV = st.s;
if (cost[cV] < cC) {
continue;
}
for (int aE : aL[cV]) {
assert(u[aE] == cV);
int aV = v[aE];
if (cost[aV] > cC + c[aE]) {
cost[aV] = cC + c[aE];
pEdge[aV] = aE;
q.push({cost[aV], aV});
}
}
}
int cV = sink;
while (cV != src) {
if (pEdge[cV] == -1) break;
sEdges.pb(pEdge[cV]);
cV = u[pEdge[cV]];
}
}
bool specEdge[MAXE];
ll g1Cost[MAXV], g2Cost[MAXV];
ll partAns[MAXE];
// compute cost for all reversed edges from src to sink
void computeCost() {
dijkstra();
// ps("fin1");
fill(specEdge, specEdge + MAXE, false);
for (int x : sEdges) {
specEdge[x] = true;
}
memcpy(g1Cost, cost, sizeof(cost));
for (int i = 0; i < E; i++) {
swap(u[i], v[i]);
}
swap(src, sink);
dijkstra();
memcpy(g2Cost, cost, sizeof(cost));
assert(g1Cost[sink] == g2Cost[src]);
for (int i = 0; i < E; i++) {
swap(u[i], v[i]);
}
swap(src, sink);
// ps("fin2");
fill(partAns, partAns + MAXE, INF);
for (int i = 0; i < E; i++) {
if (g1Cost[v[i]] < g1Cost[u[i]]) { // edge is against gradient
partAns[i] = g1Cost[v[i]] + g2Cost[u[i]] + c[i];
partAns[i] = min(partAns[i], g1Cost[sink]); // don't use reverse edge
} else {
if (specEdge) {
swap(u[i], v[i]);
dijkstra();
swap(u[i], v[i]);
partAns[i] = cost[sink];
} else {
partAns[i] = g1Cost[sink]; // just use the already found shortest path
}
}
}
}
ll ans[MAXE];
int main() {
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u[i] >> v[i] >> c[i] >> r[i];
u[i]--, v[i]--;
}
src = 0;
sink = V - 1;
computeCost();
for (int i = 0; i < E; i++) {
ans[i] = partAns[i] + r[i];
}
ans[E] = g1Cost[sink];
// ps("half");
// ps(partAns[1]);
swap(src, sink);
computeCost();
for (int i = 0; i < E; i++) {
ans[i] += partAns[i];
}
ans[E] += g1Cost[sink];
//
// ps("full");
// ps(partAns[1]);
ll fAns = INF;
for (int i = 0; i <= E; i++) {
fAns = min(fAns, ans[i]);
}
assert(fAns >= 0);
if (fAns == INF) {
fAns = -1;
}
cout << fAns << endl;
}
