#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);
vector<map<int, vector<pair<int, int>>>> spe(n);
vector<map<int, int>> per(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});
spe[u][col].emplace_back(v, w), spe[v][col].emplace_back(u, w);
per[u][col] += w, per[v][col] += w;
}
vector<map<int, int>> vsi(n);
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>>
pqpii; // [w, cur, col, cos]
pqpii.push({0, 0, m + 1, 0});
const int bign = 1e18;
vector<int> noc(n, bign);
while (!pqpii.empty()) {
auto [w, cur, col, cos] = pqpii.top();
pqpii.pop();
if (vsi[cur].count(col))
continue;
// cout << w << " " << cur << " " << col << " " << cos << "\n";
vsi[cur][col] = w;
int tot = per[cur][col];
for (auto [tow, wew] : spe[cur][col]) {
pqpii.push({w + max(0ll, tot - cos - wew), tow, m + 1, 0});
}
if (noc[cur] == bign) {
noc[cur] = w;
for (auto [tow, cow, wew] : adj[cur]) {
pqpii.push({w + wew, tow, cow, wew});
pqpii.push({w + per[cur][cow] - wew, tow, m + 1, 0});
}
}
}
int mini = noc[n - 1];
for (auto [_, val] : vsi[n - 1]) {
mini = min(mini, val);
}
if (mini == bign) {
cout << "-1\n";
} else {
cout << mini << "\n";
}
}
