from heapq import heappush, heappop
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
color_count = [{} for _ in range(n)] # Count of each color at each node
edges = []
for _ in range(m):
a, b, c, p = map(int, input().split())
a -= 1
b -= 1
adj[a].append((b, c, p))
adj[b].append((a, c, p))
edges.append((a, b, c, p))
color_count[a][c] = color_count[a].get(c, 0) + 1
color_count[b][c] = color_count[b].get(c, 0) + 1
dist = [float('inf')] * n
dist[0] = 0
pq = [(0, 0)]
while pq:
cost_u, u = heappop(pq)
if dist[u] < cost_u:
continue
for v, c, p in adj[u]:
# If the color is unique at u, we can use the edge at 0 cost
if color_count[u][c] == 1:
new_cost = cost_u
else:
# Otherwise, we must pay p to recolor
new_cost = cost_u + p
if new_cost < dist[v]:
dist[v] = new_cost
heappush(pq, (new_cost, v))
print(-1 if dist[n - 1] == float('inf') else dist[n - 1])
