import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException, FileNotFoundException {
// Scanner in = new Scanner(new File("test.in"));
Kattio in = new Kattio();
int N = in.nextInt();
int M = in.nextInt();
ArrayList<Road>[] adj = new ArrayList[N];
HashMap<Integer, Long>[] costSum = new HashMap[N];
HashMap<Integer, Long>[] dp2 = new HashMap[N];
for(int i = 0; i < N; i++){
costSum[i] = new HashMap<>();
dp2[i] = new HashMap<>();
}
for(int i = 0; i < N; i++){
adj[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++){
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
int color = in.nextInt();
int cost = in.nextInt();
adj[a].add(new Road(a, b, color, cost));
adj[b].add(new Road(b, a, color, cost));
costSum[a].put(color, costSum[a].getOrDefault(color, 0l) + cost);
costSum[b].put(color, costSum[a].getOrDefault(color, 0l) + cost);
}
long[] dp = new long[N];
Arrays.fill(dp, Integer.MAX_VALUE);
PriorityQueue<State> pq = new PriorityQueue<>();
dp[0] = 0;
pq.add(new State(0, 0, 0));
while(!pq.isEmpty()){
State curr = pq.poll();
if(curr.fromColor != 0){
if(dp2[curr.pos].get(curr.fromColor) != curr.dist){
continue;
}
for(Road r: adj[curr.pos]){
if(r.color == curr.fromColor){
long cost = costSum[r.from].get(curr.fromColor) - r.cost;
if(cost + curr.dist < dp[r.to]){
dp[r.to] = curr.dist + cost;
pq.add(new State(r.to, 0, dp[r.to]));
}
}
}
} else {
if(dp[curr.pos] != curr.dist){
continue;
}
for(Road r: adj[curr.pos]){
// don't flip this one
long cost = costSum[r.from].get(r.color) - r.cost + curr.dist;
if(cost < dp[r.to]){
dp[r.to] = cost;
pq.add(new State(r.to, 0, dp[r.to]));
}
// flip this one
cost = curr.dist + r.cost;
if(cost < dp[r.to]){
dp[r.to] = cost;
pq.add(new State(r.to, 0, dp[r.to]));
}
// flip j and another edge of the same color
cost = curr.dist;
if(!dp2[r.to].containsKey(r.color) || cost < dp2[r.to].get(r.color)){
dp2[r.to].put(r.color, cost);
pq.add(new State(r.to, r.color, cost));
}
}
}
}
System.out.println(dp[N - 1] == Integer.MAX_VALUE ? -1 : dp[N - 1]);
}
public static class State implements Comparable<State>{
int pos;
int fromColor;
long dist;
public State(int pos, int fromColor, long dist){
this.pos = pos;
this.fromColor = fromColor;
this.dist = dist;
}
public int compareTo(State s){
return Long.compare(dist, s.dist);
}
}
public static class Road {
int from, to, color, cost;
public Road(int a, int to, int color, int cost){
this.from = a;
this.to = to;
this.color = color;
this.cost = cost;
}
}
static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName + ".out"));
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}
