// Arup Guha
// 12/23/2019
// Solution to 2014 April USACO Silver Problem: Dueling GPS's

import java.util.*;
import java.io.*;

public class gpsduel {
	
	public static void main(String[] args) throws Exception {
		
		// Read in the basic graph parameters.
		BufferedReader stdin = new BufferedReader(new FileReader("gpsduel.in"));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		int n = Integer.parseInt(tok.nextToken());
		int numE = Integer.parseInt(tok.nextToken());
		ArrayList[] g1 = new ArrayList[n];
		ArrayList[] g2 = new ArrayList[n];
		
		// Here I will store the two vertices the edge is between, the two init grap weights
		// and eventually 0, 1 or 2. Namely edges[i][4] will store the number of complaints 
		// for taking edge i.
		int[][] edges = new int[numE][5];
		
		for (int i=0; i<n; i++) {
			g1[i] = new ArrayList<edge>();
			g2[i] = new ArrayList<edge>();
		}
		
		// Add the edges.
		for (int i=0; i<numE; i++) {
			tok = new StringTokenizer(stdin.readLine());
			int u = Integer.parseInt(tok.nextToken())-1;
			int v = Integer.parseInt(tok.nextToken())-1;
			int w1 = Integer.parseInt(tok.nextToken());
			int w2 = Integer.parseInt(tok.nextToken());
			g1[v].add(new edge(v, u, w1));
			g2[v].add(new edge(v, u, w2));
			edges[i][0] = v;
			edges[i][1] = u;
			edges[i][2] = w1;
			edges[i][3] = w2;
		}
		
		// Get all shortest distances from vertex n-1 on reversed graph.
		int[] dist1 = dijkstras(g1, n-1);
		int[] dist2 = dijkstras(g2, n-1);
		
		// Here we add up complaints for each edge.
		for (int i=0; i<numE; i++) {
			if (dist1[edges[i][1]] != dist1[edges[i][0]] + edges[i][2])
				edges[i][4]++;
			if (dist2[edges[i][1]] != dist2[edges[i][0]] + edges[i][3])
				edges[i][4]++;
		}
		
		// This is our last graph to run Dijkstra's on.
		ArrayList[] finalg = new ArrayList[n];
		for (int i=0; i<n; i++) finalg[i] = new ArrayList<edge>();

		// These are all the edges in the final graph.
		for (int i=0; i<numE; i++) 
			finalg[edges[i][0]].add(new edge(edges[i][0], edges[i][1], edges[i][4]));

		// This is our final Dijkstra's run.
		int[] finald = dijkstras(finalg, n-1);

		// Output to file.
		PrintWriter out = new PrintWriter(new FileWriter("gpsduel.out"));
		out.println(finald[0]);
		out.close();		
		stdin.close();
	}
	
	public static int[] dijkstras(ArrayList[] g, int source) {
		
		// Lots of set up for dijkstras.
		int n = g.length;
		int[] dist = new int[n];
		Arrays.fill(dist, -1);
		dist[source] = 0;
		
		// Add in all edges from source.
		PriorityQueue<edge> pq = new PriorityQueue<edge>();
		for (edge e: (ArrayList<edge>)g[source]) pq.offer(e);
		
		// Run till done.
		while (pq.size() > 0) {
			
			// Get next best.
			edge cur = pq.poll();
			if (dist[cur.v] != -1) continue;
			
			// If we get here this is a shortest distance.
			dist[cur.v] = cur.w;
			
			// Enqueue all new paths not to known places.
			for (edge e: (ArrayList<edge>)g[cur.v]) 
				if (dist[e.v] == -1) 
					pq.offer(new edge(e.u, e.v, cur.w+e.w));
		}
		
		// This stores all the distances.
		return dist;
	}
}

class edge implements Comparable<edge> {

	public int u;
	public int v;
	public int w;
	
	public edge(int from, int to, int weight) {
		u = from;
		v = to;
		w = weight;
	}
	
	public int compareTo(edge other) {
		return w - other.w;
	}	
}