#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int MAX = 300007;
vector<pii> G[MAX];
map<int, ll> CS[MAX];
map<ll, ll> D[MAX][2];
ll P[MAX], C[MAX];
ll Dijkstra(int N) {
memset(D, 0x3f, sizeof(D));
priority_queue<pair<ll, tuple<ll, ll, ll>>, vector<pair<ll, tuple<ll, ll, ll>>>, greater<pair<ll, tuple<ll, ll, ll>>>> PQ;
PQ.emplace(D[1][0][0] = 0, make_tuple(1, 0, 0));
while (!PQ.empty()) {
auto [cd, p] = PQ.top(); PQ.pop();
ll cur, pen, change;
tie(cur, change, pen) = p;
if (cur == N) return cd;
if (cd > D[cur][change][pen]) continue;
for (auto [next, en] : G[cur]) {
ll c0 = CS[cur][C[en]] - P[en] - (change && C[pen] == C[en] ? P[pen] : 0LL);
ll c1 = P[en];
if (cd + c0 < D[next][0][en]) {
PQ.emplace(D[next][0][en] = cd + c0, make_tuple(next, 0, en));
}
if (cd + c1 < D[next][1][en]) {
PQ.emplace(D[next][1][en] = cd + c1, make_tuple(next, 1, en));
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
ll a, b;
cin >> a >> b >> C[i] >> P[i];
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
}
for (int i = 1; i <= N; ++i) {
for (auto [_, en] : G[i]) CS[i][C[en]] += P[en];
}
cout << Dijkstra(N);
return 0;
}
