#include <bits/stdc++.h>
using namespace std;
const int N = 110000;
long long const inf = 1e16;
int n, m;
struct Edge {
int a, c;
long long p;
};
vector<Edge> v[N];
map<int, long long> ma[N];
map<int, long long> D[N];
struct Node {
int x;
long long d;
int c;
long long p;
int pa;
};
struct cmp{
bool operator() (Node u, Node v) {
return u.d > v.d;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
int a, b, c;
long long p;
for (int i = 1; i <= m; i ++) {
cin >> a >> b >> c >> p;
v[a].push_back({b, c, p});
v[b].push_back({a, c, p});
}
for (int i = 1; i <= n; i ++) {
for (Edge e : v[i]) {
if (ma[i].find(e.c) == ma[i].end()) {
ma[i][e.c] = 0;
}
ma[i][e.c] += e.p;
}
}
priority_queue<Node, vector<Node>, cmp> pq;
for (int i = 1; i <= n; i ++) {
for (Edge e : v[i]) {
D[i][e.c] = inf;
}
D[i][0] = inf;
}
D[1][0] = 0;
pq.push({1, 0, 0, 0, 0});
while (!pq.empty()) {
Node t = pq.top();
pq.pop();
if (t.d > D[t.x][t.c]) continue;
for (Edge e : v[t.x]) {
if (D[e.a][0] > t.d + e.p) {
D[e.a][0] = t.d + e.p;
pq.push({e.a, t.d + e.p, e.c, e.p, t.x});
}
if (e.c == t.c) {
if (e.a != t.pa) {
long long next_d = t.d + ma[t.x][e.c] - e.p - t.p;
if (D[e.a][e.c] > next_d) {
D[e.a][e.c] = next_d;
pq.push({e.a, next_d, 0, 0, t.x});
}
}
}
else {
long long next_d = t.d + ma[t.x][e.c] - e.p;
if (D[e.a][e.c] > next_d) {
D[e.a][e.c] = next_d;
pq.push({e.a, next_d, 0, 0, t.x});
}
}
}
}
long long ans = inf;
for (auto d : D[n]) {
ans = min(ans, d.second);
}
if (ans == inf) {
cout << -1;
return 0;
}
cout << ans;
return 0;
}
