#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
using namespace std;
const ll maxN = 1e5+5;
const ll INF = 1e18;
struct edge {
int v, c, w;
edge () {};
edge (int v, int c, ll w) : v(v), c(c), w(w) {};
void ins (int &v1, int &c1, ll &w1) {
v1 = v, c1 = c, w1 = w;
}
};
int n, m;
vector<edge> dothi[maxN];
ll d[maxN];
map<int, ll> mp[maxN], f[maxN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
fto (i, 1, m, 1) {
int u, v, c; ll w; cin >> u >> v >> c >> w;
dothi[u].emplace_back(edge(v, c, w));
dothi[v].emplace_back(edge(u, c, w));
mp[u][c] += w;
mp[v][c] += w;
}
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
pq.push({0, 1, 0});
fto (i, 1, n, 1) d[i] = INF;
d[1] = 0;
while (pq.size()) {
ll du; int u, col;
tie(du, u, col) = pq.top();
pq.pop();
if ((col == 0 && du > d[u]) || (col != 0 && du > f[u][col])) continue;
for (edge x : dothi[u]) {
int v, c; ll w; x.ins(v, c, w);
if (col) {
if (c == col) {
ll dist = du + mp[u][c] - w;
//if (u == 2 && col == 4) cout << d[u] << ' ' << c << ' ' << dist << '\n';
if (d[v] > dist) {
d[v] = dist;
pq.push({dist, v, 0});
}
}
}
else {
if (!f[v].count(c) || f[v][c] > d[u]) {
f[v][c] = d[u];
pq.push({d[u], v, c});
}
ll dist = d[u] + min(mp[u][c] - w, w);
// if (v == 4 && dist == 1) cout << u << ' ' << col << ' ' << d[u] + mp[u][c] << '\n';
if (d[v] > dist) {
d[v] = dist;
pq.push({dist, v, 0});
}
//if (u == 1 && col == 0) cout << d[u] << ' ' << c << ' ' << << '\n';
}
}
}
if (d[n] == INF) {
cout << -1 << '\n';
return 0;
}
cout << d[n] << '\n';
return 0;
}
