#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()
{
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, unsigned>> 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]++;
else
colors[u][c] = 1;
}
}
priority_queue<state> q;
q.push((state){0, m + 1, 0});
vector<map<unsigned, int64_t>> dis(n);
dis[0][m + 1] = 0;
while (!q.empty())
{
auto const [u, c0, z] = q.top();
q.pop();
auto it = dis[u].find(c0);
if (it == dis[u].end() || it->second != z)
continue;
for (auto const &[v, c, p] : g[u])
{
unsigned cc = colors[u][c];
if (cc > 1)
{
if (c == c0 && cc == 2 && (dis[v].find(c) == dis[v].end() || z < dis[v][c]))
{
dis[v][c] = z;
q.push({v, c, z});
}
if (dis[v].find(m + 1) == dis[v].end() || z + p < dis[v][m + 1])
{
dis[v][m + 1] = z + p;
q.push({v, m + 1, z + p});
}
}
else if (dis[v].find(c) == dis[v].end() || z < dis[v][c])
{
dis[v][c] = z;
q.push({v, c, z});
}
}
}
int64_t min_dis = INT64_MAX;
for (auto const [c, d] : dis[n - 1])
min_dis = min(min_dis, d);
if (min_dis == INT64_MAX)
cout << -1 << '\n';
else
cout << min_dis << '\n';
}
