import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer line = new StringTokenizer(in.readLine());
int n = Integer.parseInt(line.nextToken());
int m = Integer.parseInt(line.nextToken());
ArrayList<Edge>[] graph = new ArrayList[n];
for(int i = 0; i < n; i++) {
graph[i] = new ArrayList<Edge>();
}
for(int i = 0; i < m; i++) {
line = new StringTokenizer(in.readLine());
int a = Integer.parseInt(line.nextToken()) - 1;
int b = Integer.parseInt(line.nextToken()) - 1;
int c = Integer.parseInt(line.nextToken()) - 1;
int p = Integer.parseInt(line.nextToken());
graph[a].add(new Edge(b, c, p));
graph[b].add(new Edge(a, c, p));
}
long[] colors = new long[m];
for(int i = 0; i < n; i++) {
for(Edge e : graph[i]) {
colors[e.c] += e.p;
}
for(Edge e : graph[i]) {
e.w = colors[e.c] - e.p;
}
for(Edge e : graph[i]) {
colors[e.c] = 0;
}
}
PriorityQueue<Step> pq = new PriorityQueue<Step>();
pq.add(new Step(0, -1, 0));
long[] dp1 = new long[n];
Arrays.fill(dp1, -1);
HashMap<Integer, Long>[] dp2 = new HashMap[n];
for(int i = 0; i < n; i++) {
dp2[i] = new HashMap<Integer, Long>();
}
while(pq.size() > 0) {
Step cur = pq.poll();
if(cur.c == -1) {
if(dp1[cur.n] != -1) {
continue;
}
dp1[cur.n] = cur.d;
for(Edge e : graph[cur.n]) {
pq.add(new Step(e.to, -1, cur.d + Math.min(e.p, e.w)));
pq.add(new Step(e.to, e.c, cur.d));
}
}else {
if(dp2[cur.n].containsKey(cur.c)) {
continue;
}
dp2[cur.n].put(cur.c, cur.d);
for(Edge e : graph[cur.n]) {
if(e.c == cur.c) {
pq.add(new Step(e.to, -1, cur.d + e.w));
pq.add(new Step(e.to, e.c, cur.d + e.w));
}
}
}
}
if(dp1[n - 1] == Long.MAX_VALUE) {
out.println(-1);
}else {
out.println(dp1[n - 1]);
}
in.close();
out.close();
}
static class Step implements Comparable<Step> {
int n, c;
long d;
Step(int nn, int cc, long dd) {
n = nn;
c = cc;
d = dd;
}
@Override
public int compareTo(Step o) {
if(d > o.d) {
return 1;
}else if(d < o.d) {
return -1;
}else {
return 0;
}
}
}
static class Edge {
int to, c, p;
long w;
Edge(int t, int cc, int pp) {
to = t;
c = cc;
p = pp;
}
}
}
