#include <iostream>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 8e5 + 123;
const ll INF = 1e18 + 177013;
vector<pair<int, ll>> edg[MAXN];
vector<pair<int, pair<int, int>>> edg_init[MAXN];
signed main() {
int n, m;
cin >> n >> m;
vector<pair<pair<int, int>, pair<int, int>>> edges;
for (int i = 0; i < m; ++i) {
int a, b, c, p;
cin >> a >> b >> c >> p;
--a, --b;
edges.push_back({{c, p}, {a, b}});
edg_init[a].push_back({c, {b, p}});
edg_init[b].push_back({c, {a, p}});
}
int sz = 0;
vector<int> tin(n);
vector<int> tin_cl(n);
vector<vector<int>> clrs(n);
vector<vector<ll>> clrssm(n);
vector<vector<ll>> clrsmx(n);
for (int v = 0; v < n; ++v) {
sort(edg_init[v].begin(), edg_init[v].end());
tin[v] = sz;
tin_cl[v] = tin[v] + edg_init[v].size() + 1;
for (auto e : edg_init[v]) {
clrs[v].push_back(e.first);
}
clrs[v].resize(unique(clrs[v].begin(), clrs[v].end()) - clrs[v].begin());
clrssm[v].resize(clrs[v].size());
clrsmx[v].resize(clrs[v].size());
for (auto [c, e] : edg_init[v]) {
int ci = lower_bound(clrs[v].begin(), clrs[v].end(), c) - clrs[v].begin();
clrssm[v][ci] += e.second;
clrsmx[v][ci] = max(clrsmx[v][ci], 1ll * e.second);
}
sz += edg_init[v].size() + clrs[v].size() + 1;
for (int i = tin[v] + 1; i < sz; ++i) {
edg[i].push_back({tin[v], 0});
}
for (size_t i = 0; i < clrs[v].size(); ++i) {
edg[tin[v]].push_back({tin_cl[v] + i, clrsmx[v][i]});
}
}
//vector<map<int, int>> smp(n);
//vector<map<int, int>> mxp(n);
for (auto [vl, e] : edges) {
auto [c, p] = vl;
auto [u, v] = e;
int cv = lower_bound(clrs[v].begin(), clrs[v].end(), c) - clrs[v].begin();
int cu = lower_bound(clrs[u].begin(), clrs[u].end(), c) - clrs[u].begin();
int evu = lower_bound(edg_init[v].begin(), edg_init[v].end(), pair<int, pair<int, int>>(c, {u, p})) - edg_init[v].begin();
int euv = lower_bound(edg_init[u].begin(), edg_init[u].end(), pair<int, pair<int, int>>(c, {v, p})) - edg_init[u].begin();
//if (clrssm[v][cv] > p) {
edg[tin[v]].push_back({tin[u] + euv + 1, p});
edg[tin[v] + evu + 1].push_back({tin_cl[v] + cv, clrsmx[v][cv] - p});
edg[tin_cl[v] + cv].push_back({tin[u], clrssm[v][cv] - p - clrsmx[v][cv]});
//} else {
//edg[tin[v]].push_back({tin[u], 0});
//}
//if (clrssm[u][cu] > p) {
edg[tin[u]].push_back({tin[v] + evu + 1, p});
edg[tin[u] + euv + 1].push_back({tin_cl[u] + cu, clrsmx[u][cu] - p});
edg[tin_cl[u] + cu].push_back({tin[v], clrssm[u][cu] - p - clrsmx[u][cu]});
//} else {
//edg[tin[u]].push_back({tin[v], 0});
//}
}
//bitset<MAXN> used;
vector<ll> dist(sz, INF);
dist[0] = 0;
set<pair<ll, int>> rdist;
rdist.insert({0, 0});
while (rdist.size()) {
int v = rdist.begin()->second;
rdist.erase(rdist.begin());
//if (used[v])
//continue;
//used[v] = 1;
for (auto [u, w] : edg[v]) {
if (dist[u] > dist[v] + w) {
rdist.erase({dist[u], u});
dist[u] = min(dist[u], dist[v] + w);
rdist.insert({dist[u], u});
}
}
}
//for (int v = 0; v < n; ++v)
//cout << tin[v] << ' ';
//cout << endl;
//cout << "---" << endl;
//for (int v = 0; v < sz; ++v) {
//cout << v << ": ";
//for (auto [u, w] : edg[v])
//cout << u << ' ';
//cout << endl;
//}
//for (int v = 0; v < n; ++v)
//cout << dist[tin[v]] << ' ';
//cout << endl;
if (dist[tin[n - 1]] == INF) {
cout << "-1\n";
} else {
cout << dist[tin[n - 1]] << '\n';
}
}
