#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;
};
map<int, 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;
};
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][c].push_back({b, c, p});
v[b][c].push_back({a, c, p});
ma[a][c] += p;
ma[b][c] += p;
}
priority_queue<Node, vector<Node>, cmp> pq;
for (int i = 1; i <= n; i ++) {
dp[i] = inf;
}
dp[1] = 0;
pq.push({1, 0, 0});
while (!pq.empty()) {
Node t = pq.top();
pq.pop();
if (t.c > 0) {
if (t.d > D[t.x][t.c]) continue;
for (Edge e : v[t.x][t.c]) {
if (e.c == t.c) {
long long next_d = t.d + ma[t.x][t.c] - e.p;
if (dp[e.a] > next_d) {
dp[e.a] = next_d;
pq.push({e.a, dp[e.a], 0});
}
}
}
}
else {
if (t.d > dp[t.x]) continue;
for (auto &i : v[t.x]) {
for (Edge e : i.second) {
if (!D[e.a].count(e.c) || D[e.a][e.c] > t.d) {
D[e.a][e.c] = t.d;
pq.push({e.a, t.d, e.c});
}
long long next_d = ma[t.x][e.c] - e.p + t.d;
if (dp[e.a] > next_d) {
dp[e.a] = next_d;
pq.push({e.a, next_d, 0});
}
next_d = t.d + e.p;
if (dp[e.a] > next_d) {
dp[e.a] = next_d;
pq.push({e.a, next_d, 0});
}
}
}
}
}
if (dp[n] > inf / 2) {
cout << -1;
return 0;
}
cout << dp[n];
return 0;
}
