#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MAXM=5e5+5;
bool vis[MAXN];
int h[MAXN],e[MAXM],ne[MAXM],val[MAXM],tot;
int n,m,d[MAXN],d1[MAXN],d2[MAXN],x[MAXM],y[MAXM],v1[MAXM],v2[MAXM];
void add(int u,int v,int dis){
	val[++tot]=dis;
	e[tot]=v;
	ne[tot]=h[u];
	h[u]=tot;
}
void dijkstra(int s){
	priority_queue< pair<int,int> >q;
	memset(d,0x7f,sizeof d);
	memset(vis,0,sizeof vis);
	q.push(make_pair(0,s));d[s]=0;
	while(q.size()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		else vis[u]=1;
		for(int i=h[u];i!=-1;i=ne[i]){
			int v=e[i],dis=val[i];
			if(d[v]>d[u]+dis){
				d[v]=d[u]+dis;
				q.push(make_pair(-d[u],u));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>x[i]>>y[i]>>v1[i]>>v2[i];
	memset(h,-1,sizeof h);tot=0;
	for(int i=1;i<=m;i++) add(y[i],x[i],v1[i]);
	dijkstra(n);for(int i=1;i<=n;i++) d1[i]=d[i];
	memset(h,-1,sizeof h);tot=0;
	for(int i=1;i<=m;i++) add(y[i],x[i],v2[i]);
	dijkstra(n);for(int i=1;i<=n;i++) d2[i]=d[i];
	memset(h,-1,sizeof h);tot=0;
	for(int i=1;i<=m;i++){
		int cnt=0;
		if(d1[x[i]]!=d1[y[i]]+v1[i]) cnt++;
		if(d2[x[i]]!=d2[y[i]]+v2[i]) cnt++;
		add(y[i],x[i],cnt);
	}
	dijkstra(1);
	cout<<d[n];

	return 0;
}

不知道为什么总是输出0x7f7f7f7f（十进制下的这个数）