#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define el cout<<"\n";
#define fi first
#define se second
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
const ll INF = 1e18;
int n, m;
vector<int> topo;
vector<pair<int, pair<int, int>>> g[MAXN];
void SUB1() {
vector<ll> dp(n + 1, INF);
vector<vector<int>> dem(n + 1, vector<int>(m + 1, 0));
vector<vector<ll>> ts(n + 1, vector<ll>(m + 1, 0));
FOR(i, 1, n) {
for(auto x : g[i]) {
dem[i][x.se.fi]++;
ts[i][x.se.fi] += x.se.se;
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> p;
dp[1] = 0;
p.push({0, 1});
while(p.size()) {
pair<ll, int> x = p.top(); p.pop();
if(dp[x.se] < x.fi) continue;
for(auto y : g[x.se]) {
if(dem[x.se][y.se.fi] == 1) {
if(dp[y.fi] > x.fi) {
dp[y.fi] = x.fi;
p.push({dp[y.fi], y.fi});
}
}else {
if(dp[y.fi] > min(x.fi + y.se.se, x.fi + ts[x.se][y.se.fi] - y.se.se)) {
dp[y.fi] = min(x.fi + y.se.se, x.fi + ts[x.se][y.se.fi] - y.se.se);
p.push({dp[y.fi], y.fi});
}
}
}
}
if(dp[n] == INF) cout << -1;
else cout << dp[n];
}
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
FOR(i, 1, m) {
int x, y, c, p; cin >> x >> y >> c >> p;
g[x].push_back({y, {c, p}});
g[y].push_back({x, {c, p}});
}
if(n <= 1000 && m <= 2000) SUB1();
return 0;
}
// T.T<33~~
