#include <bits/stdc++.h>
using namespace std;
const int N = 110000;
long long const inf = 1e18;
int n, m;
struct Edge {
int a, c;
long long p;
};
vector<Edge> v[N];
map<int, long long> ma[N];
long long dp[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});
ma[a][c] += p;
ma[b][c] += p;
}
priority_queue<Node, vector<Node>, cmp> pq;
for (int i = 2; i <= n; i ++) {
for (Edge e : v[i]) {
D[i][e.c] = inf;
}
dp[i] = inf;
}
dp[1] = 0;
pq.push({1, 0, 0, 0, 0});
while (!pq.empty()) {
Node t = pq.top();
pq.pop();
if (t.c > 0 && t.d > D[t.x][t.c]) continue;
if (t.c == 0 && t.d > dp[t.x]) continue;
for (Edge e : v[t.x]) {
if (e.c == t.c) {
long long next_d = (t.d - t.p) + ma[t.x][e.c] - e.p;
if (dp[e.a] > next_d) {
dp[e.a] = next_d;
pq.push({e.a, next_d, 0, 0, t.x});
}
}
if (D[e.a][e.c] > t.d + e.p) {
D[e.a][e.c] = t.d + e.p;
pq.push({e.a, t.d + e.p, e.c, e.p, t.x});
}
if (dp[e.a] > t.d + e.p) {
dp[e.a] = t.d + e.p;
pq.push({e.a, t.d + e.p, e.c, e.p, t.x});
}
long long next_d = t.d + ma[t.x][e.c] - e.p;
if (dp[e.a] > next_d) {
dp[e.a] = next_d;
pq.push({e.a, next_d, 0, 0, t.x});
}
}
}
long long ans = dp[n];
for (auto d : D[n]) {
ans = min(ans, d.second);
}
if (ans > inf / 2) {
cout << -1;
return 0;
}
cout << ans;
return 0;
}
