#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 200005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second
vector<array<int, 3>> g[MAXN];
ll di[MAXN], S[MAXM], mn[MAXM];
bool vis[MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w, c;
cin >> u >> v >> c >> w;
g[u].push_back({v, w, c});
g[v].push_back({u, w, c});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
fill(di, di+n+1, 1e18);
di[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
ll D = pq.top().f;
ll s = pq.top().s;
pq.pop();
if (vis[s]) continue;
vis[s] = 1;
for (auto i : g[s]) mn[i[2]] = 1e18, S[i[2]] = 0;
for (auto i : g[s]) S[i[2]] += i[1];
for (auto i : g[s]) mn[i[2]] = min(mn[i[2]], di[i[0]] + S[i[2]]);
for (auto i : g[s]) {
if (di[i[0]] > min({di[s] + i[1], di[s] + S[i[2]] - i[1], mn[i[2]] - i[1]})) {
di[i[0]] = min({di[s] + i[1], di[s] + S[i[2]] - i[1], mn[i[2]] - i[1]});
pq.push({di[i[0]], i[0]});
}
}
}
cout << (di[n] > 1e15 ? -1 : di[n]) << '\n';
}
