#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 2e5 + 25;
int n, m;
vector <array <ll, 3>> adj[MAXN];
map <ll, ll> dist[MAXN][2];
priority_queue <array <ll, 4>, vector <array <ll, 4>>, greater <>> pq;
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});
}
pq.push({0, 1, 0, -1});
dist[1][0][-1] = 0;
while (!pq.empty()) {
auto k = pq.top();
pq.pop();
if (k[0] > dist[k[1]][k[2]][k[3]]) {
continue;
}
map <int, int> freq;
map <int, ll> sum;
for (auto j : adj[k[1]]) {
if (k[2]) {
if (j[0] != k[3]) {
freq[j[1]]++;
sum[j[1]] += j[2];
}
} else {
freq[j[1]]++;
sum[j[1]] += j[2];
}
}
for (auto j : adj[k[1]]) {
if (j[0] != k[3]) {
if (freq[j[1]] == 1) {
if (!dist[j[0]][0].count(k[1]) || dist[j[0]][0][k[1]] > k[0]) {
dist[j[0]][0][k[1]] = k[0];
pq.push({k[0], j[0], 0, k[1]});
}
} else {
ll c = j[2];
if (!dist[j[0]][1].count(k[1]) || dist[j[0]][1][k[1]] > k[0] + c) {
dist[j[0]][1][k[1]] = k[0] + c;
pq.push({k[0] + c, j[0], 1, k[1]});
}
c = sum[j[1]] - j[2];
if (!dist[j[0]][0].count(k[1]) || dist[j[0]][0][k[1]] > k[0] + c) {
dist[j[0]][0][k[1]] = k[0] + c;
pq.push({k[0] + c, j[0], 0, k[1]});
}
}
}
}
}
ll mn = inf;
for (auto j : adj[n]) {
if (dist[n][0].count(j[0])) mn = min(mn, dist[n][0][j[0]]);
if (dist[n][1].count(j[0])) mn = min(mn, dist[n][1][j[0]]);
}
cout << (mn == inf ? -1 : mn) << '\n';
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
