#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const long long inf = 1e18 + 7;
struct edge {
int to, color;
long long price;
int global_index;
};
struct info {
int to;
long long cost;
int index, global_index;
};
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <vector <edge> > g(n);
vector <edge> edges;
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--, b--;
g[a].push_back({b, c, p, i});
g[b].push_back({a, c, p, i});
edges.push_back({-1, c, p, i});
}
map <int, int> total_price;
vector <vector <info> > cg(n);
map <pair <int, int>, int> global;
map <pair <int, int>, int> global_rev;
map <int, int> global_price;
for (int i = 0; i < n; i++) {
for (auto [to, color, price, _] : g[i]) {
total_price[color] += price;
}
int index = 0;
for (auto [to, color, price, global_index] : g[i]) {
global[{i, index}] = global_index;
global_rev[{i, global_index}] = index;
global_price[global_index] = price;
cg[i].push_back({to, total_price[color] - price, -1, global_index});
cg[i].push_back({to, price, index, global_index});
index++;
}
for (auto [to, color, price, _] : g[i]) {
total_price[color] -= price;
}
}
priority_queue <tuple <long long, int, int> > q;
q.push({0, 0, -1});
vector <vector <long long> > d(n);
for (int i = 0; i < n; i++) {
d[i].resize((int) g[i].size() + 1, inf);
}
d[0][0] = 0;
while (!q.empty()) {
auto [cost, v, id] = q.top();
q.pop();
if (-cost > d[v][id + 1]) {
continue;
}
for (int i = 0; i < (int) cg[v].size(); i++) {
auto [to, new_cost, index, global_index] = cg[v][i];
int actual_index = -1;
if (index != -1) {
actual_index = global_rev[{to, global_index}];
} else if (id != -1) {
int global_id = global[{v, id}];
int incoming_color = edges[global_id].color;
int outgoing_color = edges[global_index].color;
if (incoming_color == outgoing_color) {
new_cost -= edges[global_id].price;
}
}
if (d[to][actual_index + 1] > d[v][id + 1] + new_cost) {
d[to][actual_index + 1] = d[v][id + 1] + new_cost;
q.push({-d[to][actual_index + 1], to, actual_index});
}
}
}
ll mn = inf;
for (int i = 0; i < (int) g[n - 1].size() + 1; i++) {
mn = min(mn, d[n - 1][i]);
}
cout << (mn == inf ? -1 : mn) << '\n';
return 0;
}
