#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<pair<int, pair<int, ll>>>> g(n + 1);
f(i, 1, m + 1) {
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
g[a].pb({b, {c, p}});
g[b].pb({a, {c, p}});
}
const ll INF = 1'420'690'000'000'069;
vector<ll> sum(m + 1, 0);
vector<ll> minn(m + 1, INF);
vector<ll> dist(n + 1, INF);
vector<ll> maks_kol(m + 1, -INF); //najmniejsz kol
priority_queue<pair<ll, int>> kolejka;
kolejka.push({0, 1});
while (!kolejka.empty()) {
ll koszt = -kolejka.top().st;
int v = kolejka.top().nd;
kolejka.pop();
if (dist[v] != INF) continue;
dist[v] = koszt;
//cout << "v to " << v << " koszt to " << koszt << "\n";
if (v == n) {cout << koszt; return 0;}
for (pair<int, pair<int, ll>> u: g[v]) {
sum[u.nd.st] += u.nd.nd;
maks_kol[u.nd.st] = max(maks_kol[u.nd.st], u.nd.nd);
minn[u.nd.st] = min(minn[u.nd.st], dist[u.st]);
}
/*f(i, 1, m + 1) {
cout << "kolor " << i << " suma " << sum[i] << " min kol " << maks_kol[i] << " minn " << minn[i] << "\n";
}*/
for (pair<int, pair<int, ll>> u: g[v]) {
ll kand = u.nd.nd + dist[v];
kand = min(kand, min(minn[u.nd.st] + sum[u.nd.st] - maks_kol[u.nd.st], dist[v] + sum[u.nd.st] - u.nd.nd));
if (dist[u.st] == INF) kolejka.push({-kand, u.st});
}
for (pair<int, pair<int, ll>> u: g[v]) {
sum[u.nd.st] = 0;
maks_kol[u.nd.st] = -INF;
minn[u.nd.st] = INF;
}
}
cout << -1;
return 0;
}
