#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int n, m;
vector<pair<int, pair<int, ll>>> graph[100001];
umap<int, ll> sums[100001];
umap<int, ll> dist[100001];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> m;
rep(i, 0, m) {
int u, v, c;
ll w;
cin >> u >> v >> c >> w;
sums[--u][--c] += w;
sums[--v][c] += w;
graph[u].pb({c, {v, w}});
graph[v].pb({c, {u, w}});
}
rep(i, 0, n) sort(all(graph[i]));
set<pair<ll, ii>> pq;
dist[0][m]=0;
pq.insert({0, {0, m}});
while (!pq.empty()) {
ll d;
int u, color;
d = pq.begin()->first;
tie(u, color) = pq.begin()->second;
pq.erase(pq.begin());
//cout<<"u = "<<u + 1<<" d = "<<d<<" color = "<<color<<endl;
if (color == m) {
trav(edge, graph[u]) {
int ncolor = edge.first, v;
ll w, sum = sums[u][ncolor];
tie(v, w) = edge.second;
ll add = min(w, sum - w);
if (!dist[v].count(m)) dist[v][m] = ll(1e16);
if (d + add < dist[v][m]) {
pq.erase({dist[v][m], {v, m}});
pq.insert({d + add, {v, m}});
dist[v][m] = d + add;
}
if (!dist[v].count(ncolor)) dist[v][ncolor] = ll(1e16);
if (d < dist[v][ncolor]) {
pq.erase({dist[v][n], {v, ncolor}});
pq.insert({d, {v, ncolor}});
dist[v][ncolor] = d;
}
}
}
else {
const auto &cur_g = graph[u];
pair<int, pair<int, ll>> x = {color, {0, 0}};
int start = lower_bound(all(cur_g), x) - cur_g.begin();
x.first++;
int stop = lower_bound(all(cur_g), x) - cur_g.begin();
rep(i, start, stop) {
int v;
ll w, sum = sums[u][color];
tie(v, w) = cur_g[i].second;
ll add = sum - w;
if (!dist[v].count(m)) dist[v][m] = ll(1e16);
if (d + add < dist[v][m]) {
pq.erase({dist[v][m], {v, m}});
pq.insert({d + add, {v, m}});
dist[v][m] = d + add;
}
}
}
}
if (!dist[n-1].count(m)) dist[n-1][m] = -1;
cout<<dist[n-1][m]<<endl;
return 0;
}
