#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define szx(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mod 1000000007
using namespace std;
int n, m;
const int MAX = 1e5 + 5;
const ll inf = 1e18;
struct Edge {
int to, c;
ll p;
};
struct PQnode {
int node, color;
ll dist;
};
vector<Edge> g[MAX];
void solve() {
cin >> n >> m;
REP(i, m) {
int a, b, c, p;
cin >> a >> b >> c >> p;
g[a].pb(Edge{b, c, p});
g[b].pb(Edge{a, c, p});
}
vector<map<int, ll>> dist(n + 1, {{0, inf}}), sumcolor(n + 1);
FOR(i, 1, n) {
sort(all(g[i]), [&](const Edge& a, const Edge& b) { return a.c < b.c; });
for (Edge e : g[i]) sumcolor[i][e.c] += e.p;
}
dist[1][0] = 0;
auto PQcmp = [&](const PQnode& A, const PQnode& B) -> bool { return A.dist > B.dist; };
priority_queue<PQnode, vector<PQnode>, decltype(PQcmp)> pq(PQcmp);
pq.push({1, 0, 0});
while (!pq.empty()) {
int u = pq.top().node;
int c = pq.top().color;
ll d = pq.top().dist;
pq.pop();
if (d > dist[u][c]) continue;
if (c == 0) {
for (Edge e : g[u]) {
ll s = sumcolor[u][e.c];
int v = e.to;
ll w = min(e.p, s - e.p);
if (!dist[v].count(0) || d + w < dist[v][0]) {
dist[v][0] = d + w;
pq.push({v, 0, d + w});
}
if (!dist[v].count(e.c) || d < dist[v][e.c]) {
dist[v][e.c] = d;
pq.push({v, e.c, d});
}
}
} else {
Edge dummy = {0, c, 0};
auto its = lower_bound(all(g[u]), dummy,
[&](const Edge& a, const Edge& b) { return a.c < b.c; });
auto ite = upper_bound(all(g[u]), dummy,
[&](const Edge& a, const Edge& b) { return a.c < b.c; });
for (auto it = its; it != ite; it++) {
int v = it->to;
ll s = sumcolor[v][c];
if (!dist[v].count(0) || d + s - it->p < dist[v][0]) {
dist[v][0] = d + s - it->p;
pq.push({v, 0, d + s - it->p});
}
}
}
}
cout << (dist[n][0] == inf ? -1 : dist[n][0]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
// freopen("main.in", "r", stdin);
// freopen("main.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--) { solve(); }
}
