#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> adj(n);
for (int i = 0; i < m; i++) {
int u, v, col, w;
cin >> u >> v >> col >> w;
u--, v--;
adj[u].push_back({v, col, w});
adj[v].push_back({u, col, w});
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
// cout << "I = " << i << "\n";
// for (auto [to, col, w] : adj[i])
// cout << to << " " << col << " " << w << "\n";
}
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>>
pqpii; // [w, cur, par]
pqpii.push({0, 0, -1});
const int bign = 1e18;
vector<vector<int>> visited(n);
for (int i = 0; i < n; i++) {
visited[i] = vector<int>(adj[i].size(), bign);
}
vector<int> neg1(n, bign);
vector<map<int, int>> vmii(n);
for (int i = 0; i < n; i++) {
for (auto [to, col, w] : adj[i]) {
vmii[i][col] += w;
}
}
while (!pqpii.empty()) {
auto [w, cur, par] = pqpii.top();
pqpii.pop();
// cout << w << " " << cur << " " << par << "\n";
if (par == -1) {
if (neg1[cur] != bign)
continue;
neg1[cur] = w;
for (int i = 0; i < adj[cur].size(); i++) {
// cout << cur << " " << i << " " << to << " " << col << " " << len <<
// "\n";
if (i == par)
continue;
auto [to, col, len] = adj[cur][i];
int in = lower_bound(adj[to].begin(), adj[to].end(),
array<int, 3>({cur, -1, -1})) -
adj[to].begin();
if (visited[to][in] == bign) {
// cout << cur << " " << i << " " << to << " " << col << " " << len
// << "\n";
pqpii.push({w + len, to, in});
}
if (neg1[to] == bign) {
pqpii.push({vmii[cur][col] - len + w, to, -1});
}
}
} else {
if (visited[cur][par] != bign) {
continue;
}
visited[cur][par] = w;
for (int i = 0; i < adj[cur].size(); i++) {
// cout << cur << " " << i << " " << to << " " << col << " " << len <<
// "\n";
if (i == par)
continue;
auto [to, col, len] = adj[cur][i];
int in = lower_bound(adj[to].begin(), adj[to].end(),
array<int, 3>({cur, -1, -1})) -
adj[to].begin();
if (visited[to][in] == bign) {
// cout << cur << " " << i << " " << to << " " << col << " " << len
// << "\n";
pqpii.push({w + len, to, in});
}
if (neg1[to] == bign) {
if (col != adj[cur][par][1]) {
pqpii.push({vmii[cur][col] - len + w, to, -1});
} else {
pqpii.push({vmii[cur][col] - len - adj[cur][par][2] + w, to, -1});
}
}
}
}
}
int mini = neg1[n - 1];
for (int i = 0; i < visited[n - 1].size(); i++) {
mini = min(mini, visited[n - 1][i]);
}
if (mini == bign) {
cout << "-1\n";
} else {
cout << mini << "\n";
}
}
