#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 1;
vector <array <int, 3>> adj[maxn];
bool processed[maxn][2];
ll dis[maxn][2];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
}
for (int i = 2; i <= n; i++)
dis[i][0] = dis[i][1] = 1e18;
priority_queue <array <ll, 4>> pq;
pq.push({0, 0, 1, 0});
ll ans = 1e18;
while (!pq.empty()) {
int s = pq.top()[2];
int col = pq.top()[1];
int p = pq.top()[3];
bool changed = (col < 0);
pq.pop();
if (s == n)
ans = min(ans, dis[s][changed]);
if (processed[s][changed])
continue;
processed[s][changed] = true;
vector <int> cnt(m+1);
vector <ll> sum(m+1);
for (auto i : adj[s]) {
if (i[0] != p || (i[0] == p && !changed)) {
cnt[i[1]]++;
sum[i[1]] += i[2];
}
}
// if (changed)
// cnt[-col]--;
for (auto i : adj[s]) {
int nxt = i[0], col2 = i[1];
if (nxt == p)
continue;
ll cost = min((ll)i[2], sum[i[1]] - i[2]);
// if ()
if (cnt[col2] == 1) {
if (dis[nxt][false] > dis[s][changed]) {
dis[nxt][false] = dis[s][changed];
pq.push({-dis[nxt][false], col2, nxt, s});
}
}
bool x = true;
if (cost == sum[i[1]] - i[2] && i[2] != sum[i[1]] - i[2])
x = false;
if (dis[nxt][x] > dis[s][changed] + cost) {
dis[nxt][x] = dis[s][changed] + cost;
if (x)
col2 = -col2;
pq.push({-dis[nxt][x], col2, nxt, s});
}
}
}
if (ans == 1e18)
ans = -1;
cout << ans << '\n';
}
