#include<bits/stdc++.h>
#define ll long long
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=10001;
int n,m,cnt;
int head[N];
ll dis1[N],dis2[N],dis3[N];
bool vis[N];
struct Edge
{
    int u,v,val1,val2;
}E[5*N];
struct edge
{
    int nex,to,from,val;
}e[N*5];
struct node
{
    ll n_dis;
    int id;
    node(int b,long long c) {n_dis=c;id=b;}
    bool operator  < ( const node &x) const
    {
        return x.n_dis>n_dis;
    }
};
void init()
{
    cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
}
void addedge(int u,int v,int val)
{
    e[++cnt].to=v;
    e[cnt].from=u;
    e[cnt].nex=head[u];
    e[cnt].val=val;
    head[u]=cnt;
}
void dijkstra(ll int *dis)
{
     int s=n;
     for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		vis[i]=0;
	}
	dis[s]=0;
	priority_queue <node> q;
	q.push(node(s,0));
	while(!q.empty())
    {
        node u=q.top();
        q.pop();
        if(vis[u.id]) continue;
        vis[u.id]=1;
        for(int i=head[u.id];i;i=e[i].nex)
        {
            int v=e[i].to;
            if(vis[v]) continue;
            if(dis[v]>dis[u.id]+e[i].val) {dis[v]=dis[u.id]+e[i].val;q.push(node(v,dis[v]));}
        }
    }
}
int main()
{
    //freopen("2.in","r",stdin);
    //freopen("3106.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        //int u,v,val1,val2;
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].val1,&E[i].val2);
        //cout<<E[i].u<<' ';
    }
    init();
    for(int i=1;i<=m;i++)
    {
        addedge(E[i].v,E[i].u,E[i].val1);
    }
    dijkstra(dis1);
    init();
     for(int i=1;i<=m;i++)
    {
        addedge(E[i].v,E[i].u,E[i].val2);
    }
    dijkstra(dis2);
    init();
    for(int i=1;i<=m;i++)
    {
        int sum=0;
        if(dis1[E[i].v]!=dis1[E[i].u]+E[i].val1) sum++;
        if(dis2[E[i].v]!=dis2[E[i].u]+E[i].val2) sum++;
        addedge(E[i].v,E[i].u,sum);
    }
    dijkstra(dis3);
    printf("%lld",dis3[1]);
    return 0;
}