//#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
for (auto &el : v) { cin >> el; }
#define cout(v) \
for (auto &el : v) { cout << el << " "; } \
cout << "\n";
using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);
#define int long long
struct edge {
int to, col, cost;
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<edge>> g(n);
for (int i = 0; i < m; i++) {
int v, u, col, cost;
cin >> v >> u >> col >> cost;
v--; u--;
g[v].push_back(edge(u, col, cost));
g[u].push_back(edge(v, col, cost));
}
map<vector<int>, int> dist;
set<pair<ll, vector<int>>> s;
// prev, cur
s.insert({0, {-1, 0, 0}});
dist[{-1, 0, 0}] = 0;
while (s.size()) {
auto el = *s.begin();
s.erase(s.begin());
int d = el.first, prev = el.second[0], cur = el.second[1], use = el.second[2];
map<int, int> mp;
map<int, int> sum;
for (edge& e : g[cur]) {
if (e.to == prev && use) {
continue;
}
mp[e.col]++;
sum[e.col] += e.cost;
}
for (edge& e : g[cur]) {
if (e.to == prev && use) {
continue;
}
if (mp[e.col] >= 2) {
if (!dist.contains({cur, e.to, 0}) || dist[{cur, e.to, 0}] > d + sum[e.col] - e.cost) {
s.erase({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
dist[{cur, e.to, 0}] = d + sum[e.col] - e.cost;
s.insert({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
}
if (!dist.contains({cur, e.to, 1}) || dist[{cur, e.to, 1}] > d + e.cost) {
s.erase({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
dist[{cur, e.to, 1}] = d + e.cost;
s.insert({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
}
} else {
if (!dist.contains({cur, e.to, 0}) || dist[{cur, e.to, 0}] > d) {
s.erase({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
dist[{cur, e.to, 0}] = d;
s.insert({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
}
if (!dist.contains({cur, e.to, 1}) || dist[{cur, e.to, 1}] > d + e.cost) {
s.erase({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
dist[{cur, e.to, 1}] = d + e.cost;
s.insert({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
}
}
}
}
ll ans = 1e18;
for (edge& e : g[n - 1]) {
if (dist.contains({e.to, n - 1, 0}) && dist[{e.to, n - 1, 0}] < ans) {
ans = dist[{e.to, n - 1, 0}];
}
if (dist.contains({e.to, n - 1, 1}) && dist[{e.to, n - 1, 1}] < ans) {
ans = dist[{e.to, n - 1, 1}];
}
}
if (ans == 1e18) ans = -1;
cout << ans << "\n";
return;
}
signed main() {
ll interactive = 0;
ll multitest = 0;
if (!interactive) {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
if (multitest) {
ll T;
cin >> T;
while (T--) {
solve();
}
} else {
solve();
}
return 0;
}
