#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<vector<int>>> g(n + 1);
for (int i = 1; i <= m; i++) {
int a, b, c, p; cin >> a >> b >> c >> p;
g[a].push_back({b, c, p});
g[b].push_back({a, c, p});
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
vector<ll> dist(n + 1, inf);
pq.push({0, 1, m + 1});
dist[1] = 0;
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
ll w = cur[0], u = cur[1], col = cur[2];
if (w > dist[u]) continue;
unordered_map<int, ll> color;
for (auto x : g[u]) color[x[1]] += x[2];
color[col]--;
for (auto x : g[u]) {
int v = x[0], c = x[1], p = x[2];
if (color[c] < 2) {
if (w < dist[v]) {
dist[v] = w;
pq.push({dist[v], v, m + 1});
}
}
else if (w + p < dist[v]) {
dist[v] = w + p;
pq.push({dist[v], v, c});
}
}
}
cout << (dist[n] == inf ? -1 : dist[n]) << '\n';
}
