#include<bits/stdc++.h>
#define ll long long
#define bit(x, i) ((x >> i) & 1)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define task "test"
using namespace std;
const int MXN = 2e5 + 5;
const int MOD = 998244353;
int n, m;
struct Adjacent {
int v, c, p;
};
vector<Adjacent> adj[MXN];
vector<pair<int, ll>> adj2[2 * MXN];
vector<pair<int, int>> col[MXN]; //col[c] = {v, p}
ll dist[2 * MXN];
bool dd[MXN];
void solve() {
cin >> n >> m;
FOR(i, 1, m) {
int u, v, c, p; cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
}
int node = n;
FOR(u, 1, n) {
vector<int> color;
for (auto v : adj[u]) {
col[v.c].push_back({v.v, v.p});
if (!dd[v.c]) {
color.push_back(v.c);
dd[v.c] = 1;
}
}
for (auto c : color) {
ll tot = 0;
for (auto ke : col[c]) tot += ke.second; //ke.first=v, ke.second=p
for (auto ke : col[c]) adj2[u].push_back({ke.first, min(1ll*ke.second, tot - ke.second)});
if (col[c].size() > 1) {
++node; //node(u,c)
for (auto ke : col[c]) {
adj2[ke.first].push_back({node, 0});
adj2[node].push_back({ke.first, tot - ke.second});
}
}
}
for (auto c : color) {
col[c].clear();
dd[c] = 0;
}
}
FOR(i, 1, node) dist[i] = 1e18;
dist[1] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 1});
while (!pq.empty()) {
ll du = pq.top().first;
int u = pq.top().second;
pq.pop();
if (du != dist[u]) continue;
for (auto v : adj2[u]) if (dist[v.first] > du + v.second) {
dist[v.first] = du + v.second;
pq.push({dist[v.first], v.first});
}
}
if (dist[n] == 1e18) cout << -1;
else cout << dist[n];
}
int32_t main() {
// if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
ios::sync_with_stdio(0); cin.tie(0);
int ntest = 1;
// cin >> ntest;
while (ntest--) solve();
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
