#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+1;
map<int, vector<pair<int, int>>> adj[N];
map<int, ll> ctotal[N], cost[N]; // cost[i][0] is no color change to i
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
while (m--) {
int a, b, c, p; cin >> a >> b >> c >> p;
adj[a][c].emplace_back(b, p);
adj[b][c].emplace_back(a, p);
ctotal[a][c] += p;
ctotal[b][c] += p;
}
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater< >> pq;
pq.emplace(0, 1, 0);
auto update = [&](int b, int c, ll d) {
if(!cost[b].count(c) || d < cost[b][c]) {
cost[b][c] = d;
pq.emplace(d, b, c);
}
};
while (!pq.empty()) {
auto[d, a, c] = pq.top();
pq.pop();
if(cost[a][c] != d) continue;
if (c == 0) {
for(auto& [color, cedges]: adj[a]) {
for(auto& [b, p] : cedges) {
update(b, 0, d + ctotal[a][color] - p);
update(b, 0, d + p);
update(b, color, d);
}
}
} else {
for(auto& [b, p] : adj[a][c])
update(b, 0, d + ctotal[a][c] - p);
}
}
cout << (cost[n].count(0) ? cost[n][0] : -1) << '\n';
}
