#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);
struct neighbour {
ll v, c, p;
};
int main() {
Algerian OI
ll n, m;
cin >> n >> m;
vector<vector<neighbour>> adj(n);
vector<map<ll, ll>> cnt(n), sum(n);
vector<ll> dis(n);
// vector<ll> c(m), p(m);
for (ll i = 0; i < m; i++) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
--a; --b; --c;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
if (cnt[a][c] == 0) dis[a]++;
if (cnt[b][c] == 0) dis[b]++;
cnt[a][c]++;
cnt[b][c]++;
sum[a][c] += p;
sum[b][c] += p;
}
for (ll i = 0; i < n; i++) {
ll mn = inf;
for (auto [col, s] : sum[i]) {
mn = min(mn, s);
}
if (dis[i] < m) mn = 0;
for (auto& [v, c, p] : adj[i]) {
// if (dis[i] == m) {
// if (cnt[i][c] == 1) p = 0;
// else p = inf;
// }
// else if (cnt[i][c] == 1) p = 0;
// if (cnt[i][c] == 1) p = 0;
// else
p = min(p + mn, sum[i][c] - p);
}
}
priority_queue<pll, vector<pll>, greater<>> pq;
vector<ll> dist(n, inf);
dist[0] = 0;
pq.push({0, 0});
while (pq.size()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto& [v, c, p] : adj[u]) {
if (d + p < dist[v]) {
dist[v] = d + p;
pq.push({dist[v], v});
}
}
}
cout << (dist[n - 1] < inf ? dist[n - 1] : -1) << "\n";
return 0;
}
