#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n, m, X[200200], Y[200200], C[200200], P[200200];
vector<array<int, 2>> v[100100];
list<array<int, 2>> l[100100];
bool chk[100100], chk2[100100];
ll d[200200][2][2], S[200200][2];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
int cnt, cur[200200][2];
ll mn[400400];
vector<array<int, 2>> v2[400400];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++) {
cin >> X[i] >> Y[i] >> C[i] >> P[i];
v[X[i]].push_back({i, 0}), v[Y[i]].push_back({i, 1});
for(int j=0;j<2;j++) d[i][j][0] = d[i][j][1] = INF;
}
for(int i=1;i<=n;i++) {
auto &V = v[i];
sort(V.begin(), V.end(), [&](const array<int, 2> &a, const array<int, 2> &b) { return tie(C[a[0]], P[a[0]]) < tie(C[b[0]], P[b[0]]); });
for(auto x : V) l[i].push_back(x);
for(int j=0;j<V.size();j++) {
int k = j;
ll sum = P[V[j][0]];
while(k+1 < V.size() && C[V[j][0]] == C[V[k+1][0]]) sum += P[V[++k][0]];
for(int l=j;l<=k;l++) {
auto [x, y] = V[l];
S[x][y] = sum, cur[x][y] = cnt, v2[cnt].push_back({x, y});
}
j = k, cnt++;
}
}
fill(mn, mn+cnt, INF);
X[0] = Y[0] = 1, pq.push({0, 0, 0, 0});
while(!pq.empty()) {
auto [cost, id, k, type] = pq.top(); pq.pop();
if(d[id][k][type] < cost) continue;
int u = k ? X[id] : Y[id];
if(u == n) return cout << cost, 0;
if(type) {
while(!l[u].empty() && C[l[u].front()[0]] != C[id]) {
auto [x, y] = l[u].front(); l[u].pop_front();
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
while(!l[u].empty() && C[l[u].back()[0]] != C[id]) {
auto [x, y] = l[u].back(); l[u].pop_back();
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
if(!chk2[u]) {
for(auto [x, y] : l[u]) {
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
chk2[u] = 1;
}
continue;
}
if(!chk[u]) {
for(auto [x, y] : v[u]) {
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
chk[u] = 1;
}
int U = cur[id][!k];
mn[U] = min(mn[U], cost-P[id]);
for(auto [x, y] : v2[U]) if(x != id) {
ll C = cost - P[id] + S[x][y] - P[x];
if(C < d[x][y][1]) d[x][y][1] = C, pq.push({C, x, y, 1});
}
// 변경된 색으로 들어와서 변경되기 전 색과 같은 간선의 색을 그대로 나가는 처리
// for(auto [x, y] : v[u]) if(x != id && C[id] == C[x]) {
// ll C = cost + S[x][y] - P[x] - P[id];
// if(C < d[x][y][1]) d[x][y][1] = C, pq.push({C, x, y, 1});
// }
}
cout << -1;
}
