#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#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;
int n, m;
map<int, vector<ii>> 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][c].emplace_back(v, w);
dothi[v][c].emplace_back(u, 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;
if (col) {
if (f[u][col] != du) continue;
for (ii x : dothi[u][col]) {
int v = x.ff; ll w = x.ss;
ll dist = du + mp[u][col] - w;
if (d[v] > dist) {
d[v] = dist;
pq.push({dist, v, 0});
}
}
}
else {
if (d[u] != du) continue;
for (pair<int, vector<ii>> pp : dothi[u]) {
int c = pp.ff;
for (ii x : pp.ss) {
int v = x.ff; ll w = x.ss;
ll dist = d[u] + min(mp[u][c] - w, w);
if (d[v] > dist) {
d[v] = dist;
pq.push({d[v], v, 0});
}
if (!f[v].count(c) || d[v] > du) {
f[v][c] = du;
pq.push({du, v, c});
}
}
}
}
}
if (d[n] == INF) {
cout << -1 << '\n';
return 0;
}
cout << d[n] << '\n';
return 0;
}
