#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int sus = 1.1e5;
const int mxn = 2.2e5;
int a[mxn], b[mxn], c[mxn], p[mxn];
vector<pii> adj[mxn];
vector<pair<int, pii>> go[mxn];
int n, m, dis[mxn];
int32_t main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i] >> p[i];
adj[a[i]].push_back(MP(i, 0));
adj[b[i]].push_back(MP(i, 0));
}
for(int i = 1; i <= n; i++) {
if(adj[i].size() == 0) continue;
// cout << "\nnode: " << i << endl;
sort(adj[i].begin(), adj[i].end(), [&] (pii pi, pii pj) {
return c[pi.ff] < c[pj.ff];
});
for(pii e : adj[i]) {
int id = e.ff;
int j = a[id] + b[id] - i;
// printf("%3d: %d -> %d (%d, %d)\n", id, i, j, c[id], p[id]);
}
int L = 0;
int col = c[adj[i][0].ff];
int cost = p[adj[i][0].ff];
vector<pair<int, pii>> vec;
for(int R = 1; R < adj[i].size(); R++) {
int id = adj[i][R].ff;
if(col == c[id]) {
cost += p[id];
}
else {
vec.push_back(MP(cost, MP(L, R - 1)));
L = R;
col = c[id];
cost = p[id];
}
}
vec.push_back(MP(cost, MP(L, adj[i].size() - 1)));
for(pair<int, pii> e : vec) {
int cost = e.ff;
int l = e.ss.ff;
int r = e.ss.ss;
for(int t = l; t <= r; t++) {
int id = adj[i][t].ff;
int rest = cost - p[id];
int j = a[id] + b[id] - i;
go[i].push_back(MP( j, MP(rest, c[id]) ));
go[i].push_back(MP( j + sus, MP(p[id], c[id]) ));
}
}
}
priority_queue<pair<pii, pii>> pq;
pq.push(MP(MP(0, 0), MP(1, -1)));
memset(dis, -1, sizeof dis);
while(pq.size()) {
int d = -pq.top().ff.ff;
int las = pq.top().ff.ss;
int cur = pq.top().ss.ff;
int col = pq.top().ss.ss;
pq.pop();
int u = (cur > sus) ? cur - sus : cur;
bool change = (cur > sus);
if(u == n) {
cout << d << endl;
return 0;
}
if(dis[cur] > -1 && dis[cur] > d) continue;
dis[cur] = d;
// cout << "\n now: " << cur << " = " << d << endl;
for(pair<int, pii> e : go[u]) {
int v = e.ff;
int w = e.ss.ff;
int c = e.ss.ss;
if(dis[v] == -1) {
int cost = d + w;
if(col == c && change && v < sus) {
cost -= las;
}
// cout << u << " -> " << v << " = " << cost << ' ' << cost - d - w << endl;
pq.push(MP(MP(-cost, w), MP(v, c)));
}
}
}
cout << -1 << endl;
return 0;
}
