#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
l << "(" << r.first << ", " << r.second << ")";
return l;
}
template <class t, unsigned long int s> ostream& operator<<(ostream &l, const array<t, s> &r) {
l << "[";
for (int i = 0; i + 1 < s; i++) l << r[i] << ", ";
if (s > 0) l << r[s - 1];
l << "]";
return l;
}
template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
l << "{";
for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
if (!r.empty()) l << r.back();
l << "}";
return l;
}
struct token {
int v, t, c;
ll w;
};
bool operator>(const token &l, const token &r) {
return l.w > r.w;
}
ostream& operator<<(ostream &l, const token &r) {
l << r.v << " " << r.t << " " << r.c << " " << r.w;
return l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<map<int, vector<pair<int, int>>>> adj(n);
vector<map<int, ll>> tot(n);
for (int i = 0; i < m; i++) {
int a, b, c, w;
cin >> a >> b >> c >> w;
a--, b--;
adj[a][c].push_back({b, w});
adj[b][c].push_back({a, w});
tot[a][c] += w;
tot[b][c] += w;
}
vector<ll> dp(n, -1);
vector<map<int, ll>> dp1(n);
priority_queue<token, vector<token>, greater<token>> pq;
pq.push({0, 0, 0, 0});
while (!pq.empty()) {
token x = pq.top();
pq.pop();
if (x.t) {
if (dp1[x.v].find(x.c) != dp1[x.v].end()) continue;
dp1[x.v][x.c] = x.w;
ll total = tot[x.v][x.c];
for (pair<int, int> &i : adj[x.v][x.c]) {
pq.push({i.first, 0, x.c, x.w + total - i.second});
}
} else {
if (dp[x.v] != -1) continue;
dp[x.v] = x.w;
for (auto& [k, v] : adj[x.v]) {
for (pair<int, int> &i : v) {
ll val = min(ll(i.second), tot[x.v][k] - i.second);
pq.push({i.first, 0, -1, x.w + val});
pq.push({i.first, 1, k, x.w});
}
}
}
}
cout << dp[n - 1] << '\n';
}
