// Robot - JOI '21
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
ArrayList<Edge>[] adj = new ArrayList[N+1];
long[] dist = new long[N+1];
HashMap<Integer, Long>[] psum = new HashMap[N+1];
Arrays.fill(dist, Long.MAX_VALUE);
for(int i = 0; i <= N; i++) {
adj[i] = new ArrayList<>();
psum[i] = new HashMap<>();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
adj[a].add(new Edge(b, c, p));
adj[b].add(new Edge(a, c, p));
add(psum[a], c, p);
add(psum[b], c, p);
}
br.close();
PriorityQueue<QueueEntry> toVisit = new PriorityQueue<>();
boolean[] mark = new boolean[N+1];
dist[1] = 0;
toVisit.add(new QueueEntry(0, new Edge(1, 0, 0)));
while(!toVisit.isEmpty()) {
QueueEntry curr = toVisit.remove();
long total = curr.total;
int id = curr.e.to, c = curr.e.c;
long p = curr.e.p; // >0 if prev node (same color as curr) was recolored
// if(mark[id]) continue; // will give incorrect answer ? disregards different e.p
if(dist[id] != total) continue;
// System.out.println("id: " + id + " total: " + total);
for(Edge e : adj[id]) {
// System.out.println("edge to " + e.to);
// Case 1: recolor e's same-colored neighbors
// if the prev node was already recolored, don't double count it
long recolor = psum[id].get(e.c) - e.p - p;
if(total + recolor < dist[e.to]) { // <= ?
dist[e.to] = total + recolor;
toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
// System.out.println("adding");
}
// Case 2: recolor e
recolor = e.p;
if(total + recolor < dist[e.to]) { // <= ?
dist[e.to] = total + recolor;
if(e.c == c) toVisit.add(new QueueEntry(dist[e.to], e));
toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
// System.out.println("adding");
}
}
}
System.out.println(dist[N] == Long.MAX_VALUE ? -1 : dist[N]);
}
public static void add(HashMap<Integer, Long> map, int c, long p) {
if(!map.containsKey(c)) map.put(c, p);
else map.replace(c, map.get(c) + p);
}
public static class Edge {
int to, c;
long p;
Edge(int to, int c, long p) {
this.to = to;
this.c = c;
this.p = p;
}
}
public static class QueueEntry implements Comparable<QueueEntry> {
long total;
Edge e;
QueueEntry(long total, Edge e) {
// total = cumulative price, e.p = price of last visited edge
this.total = total;
this.e = e;
}
public int compareTo(QueueEntry other) {
return Long.compare(total, other.total);
}
}
}
