#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int N = 2e5 + 7;
vector<tuple<int,int,long long>> g[N];
unordered_map<int,long long> dp2[N], sum[N];
long long dp[N];
int n, m;
struct Node {
int u, c;
long long dist;
bool operator < (const Node &other) const {
return dist > other.dist; // min-heap
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
long long p;
cin >> u >> v >> c >> p;
g[u].push_back({v, c, p});
g[v].push_back({u, c, p});
sum[u][c] += p;
sum[v][c] += p;
}
fill(dp + 1, dp + n + 1, INF);
dp[1] = 0;
priority_queue<Node> q;
q.push({1, 0, 0});
while (!q.empty()) {
auto [u, c, dist] = q.top(); q.pop();
if (c != 0) {
if (dp2[u][c] != dist) continue;
for (auto [v, color, p] : g[u]) if (color == c) {
long long value = dist + sum[u][color] - p;
if (dp[v] > value) {
dp[v] = value;
q.push({v, 0, dp[v]});
}
}
} else {
if (dp[u] != dist) continue;
for (auto [v, color, p] : g[u]) {
// Case 1: tô cả nhóm
long long value = dist + sum[u][color] - p;
if (dp[v] > value) {
dp[v] = value;
q.push({v, 0, dp[v]});
}
// Case 2: tô riêng
value = dist + p;
if (dp[v] > value) {
dp[v] = value;
q.push({v, 0, dp[v]});
}
// Case 3: dồn nợ
if (!dp2[v].count(color) || dp2[v][color] > dist) {
dp2[v][color] = dist;
q.push({v, color, dp2[v][color]});
}
}
}
}
cout << (dp[n] == INF ? -1 : dp[n]);
}
