import sys
from collections import defaultdict
import heapq
MOD = 1000000007
MOD2 = 998244353
def solve(cas):
n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n)]
ct = [defaultdict(list) for _ in range(n)]
sm = [defaultdict(int) for _ in range(n)]
for _ in range(m):
a, b, c, d = map(int, sys.stdin.readline().split())
a -= 1
b -= 1
g[a].append((b, c, d, 0))
g[b].append((a, c, d, 0))
ct[a][c].append(b)
ct[b][c].append(a)
sm[a][c] += d
sm[b][c] += d
heap = []
heapq.heappush(heap, (0, 0))
for i in range(n):
pt = []
for neighbor, col, cc, we in g[i]:
if len(ct[neighbor][col]) == 2:
pt.append((ct[neighbor][col][0] if ct[neighbor][col][0] != i else ct[neighbor][col][1], col, float('inf'), cc))
for x in pt:
g[i].append(x)
dp = [float('inf')] * n
dp[0] = 0
while heap:
weight, node = heapq.heappop(heap)
if dp[node] < weight:
continue
if node == n - 1:
print(weight)
return
for neighbor, col, cc, we in g[node]:
if we:
if weight + we < dp[neighbor]:
dp[neighbor] = weight + we
heapq.heappush(heap, (dp[neighbor], neighbor))
continue
if weight + min(cc, sm[node][col] - cc) * (len(ct[node][col]) > 1) < dp[neighbor]:
dp[neighbor] = weight + min(cc, sm[node][col] - cc) * (len(ct[node][col]) > 1)
heapq.heappush(heap, (dp[neighbor], neighbor))
print(-1)
def main():
t = 1
# t = int(data[0]) # Uncomment if multiple test cases are needed
for i in range(1, t + 1):
solve(i)
if __name__ == "__main__":
main()
