#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct edge{
    int u,v,p,q;
}a[50005];
struct node{
    int v,w;
    bool operator<(const node &b)const{
        return b.w<w;
    }
};
priority_queue<node>q;
vector<node>e[10005];
int dis1[10005];
int dis2[10005];
int dis3[10005];
int vis[10005];
void dij(int s,int dis[]){
    for(int i=1;i<=n;i++)dis[i]=INT_MAX;
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().v;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].v,w=e[u][i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].p>>a[i].q;
        e[a[i].v].push_back({a[i].u,a[i].p});
    }
    dij(1,dis1);
    for(int i=1;i<=n;i++)while(!e[i].empty())e[i].pop_back();
    for(int i=1;i<=m;i++)e[a[i].v].push_back({a[i].u,a[i].q});
    dij(1,dis2);
    for(int i=1;i<=n;i++)while(!e[i].empty())e[i].pop_back();
    for(int i=1;i<=m;i++){
        int cnt=0;
        if(dis1[a[i].v]-dis1[a[i].u]!=a[i].p)cnt++;
        if(dis2[a[i].v]-dis2[a[i].u]!=a[i].q)cnt++;
        e[a[i].u].push_back({a[i].v,cnt});
    }
    dij(1,dis3);
    cout<<dis3[n];
    return 0;
}