#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
struct Edge {
int to, cor, p;
Edge(int a = 0, int b = 0, int c = 0) : to(a), cor(b), p(c) {}
};
struct State {
int v, cor;
State(int a = 0, int b = 0) : v(a), cor(b) {}
bool operator < (const State& a) const {
return (make_pair(v, cor) < make_pair(a.v, a.cor));
}
};
map<int, vector<Edge>> adj[MAXN];
map<int, int> psum[MAXN], dp[MAXN];
map<int, bool> vis[MAXN], prop[MAXN];
int32_t main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a][c].push_back(Edge(b, c, p));
adj[b][c].push_back(Edge(a, c, p));
psum[a][c] += p;
psum[b][c] += p;
}
priority_queue<pair<int, State>> pq;
pq.push({0, State(1, 0)});
vis[1][0] = 1;
while (!pq.empty()) {
auto node = pq.top().second;
pq.pop();
if (prop[node.v][node.cor]) continue;
prop[node.v][node.cor] = 1;
int d = dp[node.v][node.cor];
//cout << node.v << " " << node.cor << " " << d << "\n";
if (node.cor) {
for (auto u : adj[node.v][node.cor]) {
int cost = (psum[node.v][node.cor] - u.p);
int case1 = (d + cost);
if (!vis[u.to][0] || case1 < dp[u.to][0]) {
vis[u.to][0] = 1;
dp[u.to][0] = case1;
pq.push({-case1, State(u.to, 0)});
// he pays for the previous one
}
}
} else {
for (auto &i : adj[node.v]) {
for (Edge u : i.second) {
// flip the rest
int case1 = (d + psum[node.v][u.cor] - u.p);
if (!vis[u.to][0] || case1 < dp[u.to][0]) {
vis[u.to][0] = 1;
dp[u.to][0] = case1;
pq.push({-case1, State(u.to, 0)});
}
// flip j and pay directly
int case2 = (d + u.p);
if (!vis[u.to][0] || case2 < dp[u.to][0]) {
vis[u.to][0] = 1;
dp[u.to][0] = case2;
pq.push({-case2, State(u.to, 0)});
}
// pay it forward!!
int case3 = d;
if (!vis[u.to][u.cor] || case3 < dp[u.to][u.cor]) {
vis[u.to][u.cor] = 1;
dp[u.to][u.cor] = case3;
pq.push({-case3, State(u.to, u.cor)});
}
}
}
}
}
if (!vis[n][0]) {
cout << "-1\n";
return 0;
}
cout << dp[n][0] << "\n";
}
