// Robot - JOI '21
// time complexity?
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));
// BufferedReader br = new BufferedReader(new FileReader(new File("01-09.txt")));
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];
HashMap<Integer, Long>[] psum = new HashMap[N+1];
long[] dist = new long[N+1];
HashMap<Integer, Long>[] dist2 = 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<>();
dist2[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();
// continue modeling solution
PriorityQueue<QueueEntry> toVisit = new PriorityQueue<>();
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, p = curr.e.p;
// System.out.println("curr.e: " + curr.e);
for(Edge e : adj[id]) {
// System.out.println("edge to: " + e.to);
if(p > 0) { // special case - we already flipped prev edge ?????
// System.out.println("id: " + id + " c: " + c);
if(c != e.c ||
total != dist2[id].get(c)) continue;
long recolor = psum[id].get(e.c) - e.p;
if(total + recolor < dist[e.to]) {
dist[e.to] = total + recolor;
// System.out.println("1: " + dist[e.to]);
toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
}
} else {
if(total != dist[id]) continue;
// System.out.println("got here");
// Case 1: recolor e's same-colored neighbors
long recolor = psum[id].get(e.c) - e.p;
if(total + recolor < dist[e.to]) {
dist[e.to] = total + recolor;
// System.out.println("2: " + dist[e.to]);
toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
}
// Case 2: only recolor e
recolor = e.p;
if(total + recolor < dist[e.to]) {
dist[e.to] = total + recolor;
// System.out.println("4: " + dist[e.to]);
toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
}
// Case 3: recolor curr and e
recolor = e.p;
if(!dist2[e.to].containsKey(e.c) || total < dist2[e.to].get(e.c)) {
add(dist2[e.to], e.c, total);
// System.out.println("e.to: " + e.to + " e.c: " + e.c + " total: " + total);
// System.out.println("3: " + dist[e.to]);
toVisit.add(new QueueEntry(dist2[e.to].get(e.c), e));
}
}
}
}
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, p;
Edge(int to, int c, int p) {
this.to = to;
this.c = c;
this.p = p;
}
public String toString() { return "id: " + to + " c: " + c + " 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);
}
}
}
/*
4 6
1 4 4 1
3 4 1 1
1 3 4 1
2 4 3 1
2 3 3 1
1 2 4 1
4 4
1 2 3 1
2 3 2 1
3 4 1 1
1 4 2 1
*/
