#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MX = 1e5 + 5;
struct Edge
{
int u;
int color;
ll price;
};
// vector<pair<int, ll>> adj[MX];
vector<Edge> adj[MX];
int A[MX], B[MX], C[2 * MX];
ll P[2 * MX];
ll dist[MX];
map<int, int> colors[MX];
int N, M;
int main()
{
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> A[i] >> B[i] >> C[i] >> P[i];
adj[A[i]].push_back({B[i], C[i], P[i]});
adj[B[i]].push_back({A[i], C[i], P[i]});
// colors[A[i]].insert(C[i]);
// colors[B[i]].insert(C[i]);
colors[A[i]][C[i]]++;
colors[B[i]][C[i]]++;
}
using T = pair<ll, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 1});
for (int i = 1; i <= N; i++)
dist[i] = LONG_LONG_MAX;
dist[1] = 0;
while (!pq.empty())
{
auto curr = pq.top();
pq.pop();
int v = curr.second;
if (dist[v] < curr.first)
continue;
for (auto e : adj[v])
{
// ll w = (colors[v].find(e.color) == colors[v].end() ? 0 : e.price);
ll w = (colors[v][e.color] == 1 ? 0 : e.price);
if (dist[v] + w < dist[e.u])
{
dist[e.u] = dist[v] + w;
pq.push({dist[e.u], e.u});
}
}
}
if (dist[N] == LONG_LONG_MAX)
cout << -1 << '\n';
else
cout << dist[N] << '\n';
return 0;
}
