#include <bits/stdc++.h>
using namespace std;
struct edge
{
unsigned v, c;
int64_t p;
};
struct state
{
unsigned u, c;
int64_t z;
bool operator<(state const &s) const
{
return z > s.z;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
unsigned n, m;
cin >> n >> m;
vector<vector<edge>> g(n);
for (size_t i = 0; i < m; i++)
{
unsigned u, v, c;
int64_t p;
cin >> u >> v >> c >> p;
g[u - 1].push_back({v - 1, c, p});
g[v - 1].push_back({u - 1, c, p});
}
vector<map<unsigned, int64_t>> colors(n);
for (unsigned u = 0; u < n; u++)
{
for (auto const &[v, c, p] : g[u])
{
if (colors[u].find(c) != colors[u].end())
colors[u][c] += p;
else
colors[u][c] = p;
}
}
priority_queue<state> q;
q.push((state){0, m + 1, 0});
vector<int64_t> dp1(n, INT64_MAX);
vector<map<unsigned, int64_t>> dp2(n);
dp1[0] = 0;
while (!q.empty())
{
dp2[0][m + 1] = 0;
auto const [u, c0, z] = q.top();
q.pop();
if (c0 < m + 1)
{
// Consider the case that a edge was just flipped, and for the next
// edge, all other edges except the flipped one must be flipped.
if (dp2[u][c0] != z)
continue;
for (auto const &[v, c, p] : g[u])
{
if (c == c0 && z + colors[u][c] - p < dp1[v])
{
dp1[v] = z + colors[u][c] - p;
q.push({v, m + 1, dp1[v]});
}
}
}
else
{
if (dp1[u] != z)
continue;
for (auto const &[v, c, p] : g[u])
{
if (z + colors[u][c] - p < dp1[v])
{
dp1[v] = z + colors[u][c] - p;
q.push({v, m + 1, dp1[v]});
}
if (z + p < dp1[v])
{
dp1[v] = z + p;
q.push({v, m + 1, z + p});
}
if (dp2[v].find(c) == dp2[v].end() || z < dp2[v][c])
{
dp2[v][c] = z;
q.push({v, c, z});
}
}
}
}
if (dp1[n - 1] == INT64_MAX)
cout << -1 << '\n';
else
cout << dp1[n - 1] << '\n';
}
