#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back
struct segTree
{
vector<int> tree;
int sz = 0;
void init(int n)
{
sz = n;
tree.resize(2 * sz, 0);
}
void set(int pos, int val)
{
pos += sz;
tree[pos] = val;
pos >>= 1;
while (pos)
{
tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
pos >>= 1;
}
}
int get(int l, int r)
{
int res = 0;
l += sz;
r += sz;
while (l < r)
{
if (l & 1)
res += tree[l++];
if (r & 1)
res += tree[--r];
l >>= 1;
r >>= 1;
}
return res;
}
};
#define int ll
const ll INF = 1e18 + 10;
struct test
{
vector<pii> E;
vector<int> C, P;
vector<vector<int>> graph;
vector<set<int>> ngraph;
void solve()
{
int n, m;
cin >> n >> m;
vector<pii> edges;
vector<map<int, ll>> cost(n);
map<pii, vector<int>> edgesVCol;
graph.resize(n);
ngraph.resize(n);
for (int i = 0; i < m; ++i)
{
int v, tov, c, p;
cin >> v >> tov >> c >> p;
--v, --tov, --c;
E.pb({v, tov});
C.pb(c);
P.pb(p);
cost[v][c] += p;
cost[tov][c] += p;
graph[v].pb(i);
graph[tov].pb(i);
ngraph[v].insert(i);
ngraph[tov].insert(i);
edgesVCol[{v, c}].pb(i);
edgesVCol[{tov, c}].pb(i);
}
int res = INF;
priority_queue<pair<int, pair<pii, int>>> els;
map<pii, int> costs;
map<pii, int> OUT;
for (int i = 0; i <= m; ++i)
{
costs[{0, i}] = 0;
OUT[{0, i}] = 0;
}
els.push({-0, {{0, m}, 0}});
while (els.size())
{
auto [c, WTF] = els.top();
auto [inf, t] = WTF;
els.pop();
c = -c;
auto [v, col] = inf;
if (!t)
{
if (v == n - 1)
res = min(res, c);
if (costs[inf] != c)
continue;
auto it = ngraph[v].begin();
while (it != ngraph[v].end())
{
int tov = E[*it].f == v ? E[*it].s : E[*it].f;
if (col != C[*it])
{
if (costs.find({tov, C[*it]}) == costs.end() or costs[{tov, C[*it]}] > c + min(P[*it], cost[v][C[*it]] - P[*it]))
{
costs[{tov, C[*it]}] = c + min(P[*it], cost[v][C[*it]] - P[*it]);
els.push({-costs[{tov, C[*it]}], {{tov, C[*it]}, 0}});
}
}
if (OUT.find({tov, C[*it]}) == OUT.end() or OUT[{tov, C[*it]}] > c)
{
OUT[{tov, C[*it]}] = c;
els.push({-OUT[{tov, C[*it]}], {{tov, C[*it]}, 1}});
}
if (col != C[*it])
it = ngraph[v].erase(it);
else
{
it = next(it);
}
}
}
else
{
if (OUT[{v, col}] != c)
continue;
for (auto id : edgesVCol[{v, col}])
{
int tov = E[id].f == v ? E[id].s : E[id].f;
if (costs.find({tov, col}) == costs.end() or costs[{tov, col}] > c + min(P[id], cost[v][col] - P[id]))
{
costs[{tov, col}] = c + min(P[id], cost[v][col] - P[id]);
els.push({-costs[{tov, col}], {{tov, col}, 0}});
}
}
}
}
cout << (res == INF ? -1 : res) << "\n";
}
};
main()
{
test t;
t.solve();
}
