#include <bits/stdc++.h>
using namespace std;
struct edge {
int to, color, cost;
long long total;
edge(int _to, int _color, int _cost) {
to = _to;
color = _color;
cost = _cost;
total = 0;
}
bool operator < (const edge& e) const {
return color < e.color;
}
};
struct item {
long long path;
int from;
int to;
int cost;
int color;
item(long long _path, int _from, int _to, int _cost, int _color) {
path = _path;
from = _from;
to = _to;
cost = _cost;
color = _color;
}
bool operator < (const item& a) const {
return path > a.path;
}
};
int n, m;
vector<vector<edge>> adj;
int main() {
cin >> n >> m;
adj.resize(n);
for (int i = 0; i < m; i++) {
int u, v, color, cost;
cin >> u >> v >> color >> cost;
u--; v--;
adj[u].emplace_back(v, color, cost);
adj[v].emplace_back(u, color, cost);
}
for (int u = 0; u < n; u++) {
vector<edge> &edges = adj[u];
long long total = 0;
sort(edges.begin(), edges.end());
for (int i = 0; i < edges.size(); i++) {
if (i == 0 || edges[i].color != edges[i - 1].color) {
total = edges[i].cost;
for (int j = i + 1; j < edges.size(); j++) {
if (edges[j].color != edges[i].color) break;
total += edges[j].cost;
}
// cout << u + 1 << ' ' << edges[i].color << ' ' << total << endl;
}
edges[i].total = total;
}
}
priority_queue<item> q;
//(long long _path, int _from, int _to, int _cost, int _color)
q.emplace(0, -1, 0, 0, 0);
// q.emplace(0, -1, 1, 0, 0);
// vector<bool> vis(2 * n + 2, 0);
set<pair<int, int>> vis;
int ans = -1;
while (!q.empty()) {
item curr = q.top(); q.pop();
int u1 = curr.to;
int path = curr.path;
int p = curr.from;
int from_cost = curr.cost;
int from_color = curr.color;
int u = u1 / 2;
// printf("%d to %d: %d\n", p, u1, path);
// cout << u + 1 << " "<< u1 << " " << path << endl;
if (vis.find({p, u1}) != vis.end()) continue;
vis.insert({p, u1});
// if (vis[u1]) continue;
// vis[u1] = 1;
// cout << p << " to " << u + 1 << () << " dist: " << path << endl;
if (u == n - 1) { ans = path; break; }
for (edge &e : adj[u]) {
int v = e.to;
int to_color = e.color;
int to_cost = e.cost;
long long total = e.total;
int v1 = 2 * v;
// if (!vis[v1]) {
// real
int cost = total - to_cost;
if (u1 & 1) {
if (from_color == to_color) cost -= from_cost;
q.emplace(path + cost, u1, v1, cost, to_color);
} else { // real to real: real
if (from_color != to_color) {
q.emplace(path + cost, u1, v1, cost, to_color);
}
}
// }
int v2 = 2 * v + 1;
// if (!vis[v2]) {
// fake
// if (v2 == 23) cout << "::: " << to_cost << "L " << path + to_cost << endl;
q.emplace(path + to_cost, u1, v2, to_cost, to_color);
// }
}
}
cout << ans << endl;
return 0;
}
