#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, color, cost;
};
struct State {
int node, cost;
bool operator>(const State &other) const {
return cost > other.cost;
}
};
const int INF = 1e9;
int N, M;
vector<Edge> adj[1005];
map<int, vector<int>> color_adj[1005];
int dijkstra() {
priority_queue<State, vector<State>, greater<State>> pq;
vector<int> minCost(N + 1, INF);
pq.push({1, 0});
minCost[1] = 0;
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
int u = cur.node, cur_cost = cur.cost;
if (u == N) return cur_cost;
for (auto &edge : adj[u]) {
int v = edge.to, c = edge.color, p = edge.cost;
if (color_adj[u][c].size() > 1) continue; // Ambiguous color
if (cur_cost + p < minCost[v]) {
minCost[v] = cur_cost + p;
pq.push({v, minCost[v]});
}
}
}
return -1;
}
int main() {
cin >> N >> M;
vector<tuple<int, int, int, int>> edges;
for (int i = 0; i < M; i++) {
int A, B, C, P;
cin >> A >> B >> C >> P;
edges.push_back({A, B, C, P});
adj[A].push_back({B, C, P});
adj[B].push_back({A, C, P});
color_adj[A][C].push_back(B);
color_adj[B][C].push_back(A);
}
int result = dijkstra();
cout << result << endl;
return 0;
}
