#include <bits/stdc++.h>
using namespace std;
#define FILE "TEST"
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fi first
#define se second
const int MaxN = 1E5 + 15;
const long long INF = 9E18;
struct Edge {
int to, c;
long long d;
};
map <int, vector <Edge>> G[MaxN];
long long dp[MaxN];
map <int, long long> f[MaxN], sumd[MaxN];
map <int, vector <Edge>>::iterator it;
int n, m, u, v, c, d;
typedef tuple <long long, int, int> T;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if (fopen(FILE".INP", "r")) {
freopen(FILE".INP", "r", stdin);
freopen(FILE".OUT", "w", stdout);
}
cin >> n >> m;
while (m--) {
cin >> u >> v >> c >> d;
G[u][c].push_back({v, c, d});
G[v][c].push_back({u, c, d});
sumd[u][c] += d;
sumd[v][c] += d;
}
for (int i = 1; i <= n; i++) dp[i] = INF;
dp[1] = 0;
priority_queue <T> Q;
Q.emplace(0, 1, 0);
while (Q.size()) {
long long w;
int u, c;
tie(w, u, c) = Q.top();
Q.pop();
if (c) {
if (f[u][c] != -w) continue;
for (Edge E : G[u][c]) {
long long cost = sumd[u][c] - E.d - w;
if (dp[E.to] > cost) {
dp[E.to] = cost;
Q.emplace(-dp[E.to], E.to, 0);
}
}
}
else {
if (dp[u] != -w) continue;
for (it = G[u].begin(); it != G[u].end(); it++)
for (Edge E : it->second) {
long long cost;
cost = sumd[u][E.c] - E.d - w;
if (dp[E.to] > cost) {
dp[E.to] = cost;
Q.emplace(-dp[E.to], E.to, 0);
}
cost = E.d - w;
if (dp[E.to] > cost) {
dp[E.to] = cost;
Q.emplace(-dp[E.to], E.to, 0);
}
cost = -w;
if (!f[E.to].count(E.c) || f[E.to][E.c] > cost) {
f[E.to][E.c] = cost;
Q.emplace(-f[E.to][E.c], E.to, E.c);
}
}
}
}
cout << (dp[n] == INF ? -1 : dp[n]);
return 0;
}
