#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
using namespace std;
#define int long long
#define app push_back
#define all(x) x.begin(), x.end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' '; cout << endl; } while(0)
#else
#define debug(...)
#define debugv(v)
#endif
int32_t main() {
cin.tie(0);ios_base::sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector <vector <int> > e(n);
int sz = n + 6 * m;
vector <vector <pair <int, int> > > g(sz);
vector <int> a(m), b(m), color(m), price(m);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v >> color[i] >> price[i];
color[i]--;
u--; v--;
a[i] = u;
b[i] = v;
e[u].app(i);
e[v].app(i);
}
auto num = [&] (int i, int from, int change) {
return n + m * (2 * (from == a[i]) + change) + i;
};
auto edge = [&] (int u, int v, int c) {
g[u].app({v,c});
};
vector <vector <int> > who(m);
int ptr = n + 4 * m;
for (int u = 0; u < n; ++u) {
vector <int> cs;
for (int i : e[u]) {
edge(num(i, a[i]^b[i]^u, 0), u, 0);
edge(num(i, a[i]^b[i]^u, 1), u, 0);
edge(u, num(i, u, 1), price[i]);
who[color[i]].app(i);
cs.app(color[i]);
}
for (int col : cs) {
if (!who[col].empty()) {
int sum = 0;
for (int i : who[col]) {
sum += price[i];
}
for (int i : who[col]) {
edge(u, num(i, u, 0), sum - price[i]);
}
if (who[col].size() > 1) {
int f = who[col].front();
for (int i : who[col]) {
if (price[i] > price[f]) {
f = i;
}
}
for (int e : who[col]) {
if (e != f) {
edge(num(e, a[e]^b[e]^u, 1), num(f, u, 0),
sum - price[e] - price[f]);
edge(num(f, a[f]^b[f]^u, 1), num(e, u, 0),
sum - price[e] - price[f]);
}
}
int uu = ptr++;
for (int e : who[col]) {
if (e != f) {
edge(num(e, a[e]^b[e]^u, 1), uu, price[f] - price[e]);
edge(uu, num(e, u, 0), sum - price[f] - price[e]);
}
}
}
who[col].clear();
}
}
}
const int inf = 1e18;
vector <int> dist(sz, inf);
dist.front() = 0;
priority_queue <pair <int, int>,
vector <pair <int, int> > , greater <pair <int, int> > > q;
q.push({0,0});
while (!q.empty()) {
auto [d, u] = q.top(); q.pop();
if (d != dist[u]) {
continue;
}
//debug(d,u);
for (auto [v, c] : g[u]) {
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
q.push({dist[v], v});
}
}
}
if (dist[n - 1] == inf) {
cout << -1 << '\n';
}
else {
cout << dist[n - 1] << '\n';
}
}
