import java.io.*;
import java.util.*;
public class Main {
public static int num; public static int m;
public static HashMap<Integer, Long>[] costs;
public static void main(String[] args) throws IOException {
FastIO io = new FastIO();
num = io.nextInt(); m = io.nextInt();
ArrayList<ArrayList<Edge>> adj = new ArrayList<>(); costs = new HashMap[num];
for (int i = 0;i<num;i++) {
adj.add(new ArrayList<>()); costs[i] = new HashMap<>();
}
for (int i = 0;i<m;i++) {
int a = io.nextInt()-1; int b = io.nextInt()-1; int c = io.nextInt(); int d = io.nextInt();
adj.get(a).add(new Edge(b,c,d)); adj.get(b).add(new Edge(a,c,d));
costs[a].put(c, costs[a].getOrDefault(c,0L)+d); costs[b].put(c, costs[b].getOrDefault(c,0L)+d);
}
long ans = dijkstra(adj);
if (ans==Long.MAX_VALUE) io.println(-1);
else io.println(ans);
io.close();
}
public static long dijkstra (ArrayList<ArrayList<Edge>> adj) {
HashMap<Integer, Long>[][] dis = new HashMap[num][2];
for (int i = 0;i<num;i++) {dis[i][0] = new HashMap<>(); dis[i][1] = new HashMap<>();}
dis[0][0].put(-1,0L); dis[0][1].put(-1,0L);
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(i -> i.cost));
pq.add(new Node(0,new Edge(-1,0,0),0,false));
while (!pq.isEmpty()) {
//System.out.println(pq);
Node curr = pq.poll(); int node = curr.n; long d = curr.cost; Edge prev = curr.prev; boolean change = curr.change;
if (dis[node][toI(change)].get(prev.n)!=d) continue;
for (Edge e : adj.get(node)) {
int n = e.n; int c = e.c; long w = e.w;
if (n==prev.n) continue;
long newD1 = d; long newD0 = d; //1 -> New change true; 0 -> New change false.
if (change&&prev.c==c) {
newD1 += w; newD0 += costs[node].get(c)-prev.w-w;
} else {
newD1 += w; newD0 += costs[node].get(c)-w;
}
if (newD0<dis[n][0].getOrDefault(node, Long.MAX_VALUE)) {
dis[n][0].put(node, newD0);
pq.add(new Node(n,new Edge(node,c,w),newD0,false));
}
if (newD1<dis[n][1].getOrDefault(node, Long.MAX_VALUE)) {
dis[n][1].put(node,newD1);
pq.add(new Node(n,new Edge(node,c,w),newD1,true));
}
}
}
long ans = Long.MAX_VALUE;
for (Edge e : adj.get(num-1)) ans = Math.min(ans, Math.min(dis[num-1][0].getOrDefault(e.n, Long.MAX_VALUE),dis[num-1][1].getOrDefault(e.n, Long.MAX_VALUE)));
return ans;
}
public static class Edge {
int n; int c; long w;
Edge (int n, int c, long w) {
this.n = n; this.c = c; this.w = w;
}
}
public static class Node {
int n; Edge prev; long cost; boolean change;
Node (int n, Edge prev, long cost, boolean change) {
this.n = n; this.prev = prev; this.cost = cost; this.change = change;
}
}
public static int toI (boolean b) {
return b ? 1 : 0;
}
public static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
public FastIO() { this(System.in, System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
private int nextByte() {
if (numChars == -1) { throw new InputMismatchException(); }
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) { throw new InputMismatchException(); }
if (numChars == -1) {
return -1; // end of file
}
}
return buf[curChar++];
}
public int nextInt() {
int c;
do { c = nextByte(); } while (c <= ' ');
int sgn = 1;
if (c == '-') { sgn = -1; c = nextByte(); }
int res = 0;
do {
if (c < '0' || c > '9') { throw new InputMismatchException(); }
res = 10 * res + c - '0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
}
}
