#include <bits/stdc++.h>
#define pb push_back
#define st first
#define nd second
using ll = long long;
using ld = long double;
using namespace std;
struct edge {
int to, c;
ll p;
edge(int to = 0, int c = 0, ll p = 0) : to(to), c(c), p(p) {}
};
const ll INF = 1e16;
const int MN = 100005;
int n, m;
map <int, vector <edge> > v[MN];
map <int, vector <edge> > vec[MN];
map <int, bool> visited[MN];
map <int, ll> p_sum[MN], dp[MN]; // suma kosztow p dla koloru c | minimalny koszt dotarcia do wierzchołka v krawędzią o kolorze c
// X: pokoloruj krawędź
// Y: pokoloruj wszystkie inne
priority_queue <pair<ll, pair <int, int> > > pq; // koszt, wierzchołek, kolor
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
v[a][0].pb(edge(b, c, p)); // Y: a -> b
v[b][0].pb(edge(a, c, p)); // X: b -> a
p_sum[a][c] += p;
p_sum[b][c] += p;
}
for(int i = 1; i <= n; i++) {
dp[i][0] = INF;
vector <edge> ve = v[i][0];
vec[i][0] = ve;
for(int ii = 0; ii < (int)ve.size(); ii++) {
dp[i][ve[ii].c] = INF;
// from = i, to = ve[ii].to, colour = c, price = p
vec[i][0].pb(edge(ve[ii].to, 0, ve[ii].p)); // v -> w (normalna)
vec[i][0].pb(edge(ve[ii].to, ve[ii].c, 0)); // v -> e,c (koszt 0)
vec[i][0].pb(edge(i, ve[ii].c, 0)); // v -> v,c (koszt 0)
vec[ve[ii].to][0].pb(edge(ve[ii].to, ve[ii].c, 0)); // w -> e,c (koszt 0)
vec[ve[ii].to][ve[ii].c].pb(edge(i, 0, p_sum[ve[ii].to][ve[ii].c] - ve[ii].p)); // e,c -> v (koszt sum_p - koszt_p_kr)
}
}
dp[1][0] = 0;
pq.push({0, {1, 0}});
while(!pq.empty()) {
pair <int, int> x = pq.top().nd; // wierzchołek kolor
pq.pop();
if(!visited[x.st][x.nd]) {
visited[x.st][x.nd] = 1;
ll koszt = dp[x.st][x.nd];
// cout << x.st << ' ' << x.nd << " = " << koszt << "\n";
vector <edge> ve = vec[x.st][x.nd];
for(int i = 0; i < (int)ve.size(); i++) {
if(!visited[ve[i].to][ve[i].c] && koszt + ve[i].p < dp[ve[i].to][ve[i].c]) {
dp[ve[i].to][ve[i].c] = koszt + ve[i].p;
pq.push({-(koszt + ve[i].p), {ve[i].to, ve[i].c}});
}
}
}
}
// for(int i = 1; i <= n; i++) {
// cout << "---------- " << i << " -----------\n";
// for(int ii = 0; ii < vec[i][0].size(); ii++) {
// cout << i << " ---> " << vec[i][0][ii].to << " (" << vec[i][0][ii].c << ',' << vec[i][0][ii].p << ")\n";
// }
// }
if(dp[n][0] == INF) {
cout << "-1";
}
else {
cout << dp[n][0];
}
return 0;
}
