#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 25;
int n, m;
vector <array <int, 3>> adj[MAXN];
map <int, vector <array <int, 2>>> adj2[MAXN];
int dist[MAXN];
map <int, int> dist2[MAXN];
map <int, int> sum[MAXN];
void solve () {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c, d; cin >> a >> b >> c >> d;
adj[a].push_back({b, c, d});
adj[b].push_back({a, c, d});
adj2[a][c].push_back({b, d});
adj2[b][c].push_back({a, d});
sum[a][c] += d;
sum[b][c] += d;
}
priority_queue <array <int, 3>, vector <array <int, 3>>, greater <>> pq;
pq.push({0, 1, 0});
for (int i = 2; i <= n; i++) {
dist[i] = 1e18;
}
for (int i = 1; i <= n; i++) {
for (auto j : adj[i]) {
dist2[i][j[1]] = 1e18;
}
}
while (!pq.empty()) {
auto k = pq.top();
pq.pop();
if (k[2] == 0) {
if (k[0] > dist[k[1]]) {
continue;
}
for (auto j : adj[k[1]]) {
if (dist[j[0]] > sum[k[1]][j[1]] - j[2] + k[0]) {
dist[j[0]] = sum[k[1]][j[1]] - j[2] + k[0];
pq.push({dist[j[0]], j[0], 0});
}
if (dist[j[0]] > j[2] + k[0]) {
dist[j[0]] = j[2] + k[0];
pq.push({dist[j[0]], j[0]});
}
if (dist2[j[0]][j[1]] > k[0]) {
dist2[j[0]][j[1]] = k[0];
pq.push({k[0], j[0], j[1]});
}
}
} else {
if (k[0] > dist2[k[1]][k[2]]) {
continue;
}
for (auto j : adj2[k[1]][k[2]]) {
if (k[0] + sum[k[1]][k[2]] - j[1] < dist[j[0]]) {
dist[j[0]] = k[0] + sum[k[1]][k[2]] - j[1];
pq.push({dist[j[0]], j[0], 0});
}
}
}
}
cout << (dist[n] >= (int)(1e18) ? -1 : dist[n]) << '\n';
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
