rt

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
inline int read() {
	int x=0;
	short f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
int n,m;
const int N=5e5+10;
int head[N],x[N],y[N],v1[N],v2[N],dis[N],dis1[N],dis2[N],tot;
bool vis[N];
struct qq {
	int to,v,nxt;
} e[N];
struct node {
	int i,dis;
	bool operator < (const node &x) const {
		return x.dis<dis;
	}
};
void add(int x,int y,int v1) {
	e[++tot].to=y;
	e[tot].v=v1;
	e[tot].nxt=head[x];
	head[x]=tot;
}
priority_queue <node> q;
void dij(int s) {
	for(int i=1; i<=n; i++) {
		dis[i]=0x3f3f3f3f;
		vis[i]=0;
	}
	dis[s]=0;
	q.push((node) {
		s,0
	});
	while(!q.empty()) {
		node p=q.top();
		q.pop();
		if(vis[p.i])
			continue;
		vis[p.i]=1;
		for(int i=head[p.i]; i; i=e[i].nxt) {
			if(dis[e[i].to]>dis[p.i]+e[i].v) {
				dis[e[i].to]=dis[p.i]+e[i].v;
				q.push((node) {
					e[i].to,dis[e[i].to]
				});
			}
		}
	}
}
int main() {
	n=read();
	m=read();
	for(int i=1; i<=m; i++) {
		x[i]=read(),y[i]=read(),v1[i]=read(),v2[i]=read();
		add(y[i],x[i],v1[i]);
	}
	dij(n);
	for(int i=1; i<=n; i++)
		dis1[i]=dis[i];
	memset(head,0,sizeof(head));
	tot=0;
	for(int i=1; i<=m; i++)
		add(y[i],x[i],v2[i]);
	dij(n);
	for(int i=1; i<=n; i++)
		dis2[i]=dis[i];
	memset(head,0,sizeof(head));
	tot=0;
	for(int i=1; i<=m; i++) {
		if(dis1[y[i]]+v1[i]!=dis1[x[i]]&&dis2[y[i]]+v2[i]!=dis2[x[i]])
			add(y[i],x[i],2);
		else if(dis1[y[i]]+v1[i]!=dis1[x[i]]||dis2[y[i]]+v2[i]!=dis2[x[i]])
			add(x[i],y[i],1);
		else
			add(x[i],y[i],0);
//		int sum=0;
//		if(dis1[x[i]]!=dis1[y[i]]+v1[i])sum++;
//		if(dis2[x[i]]!=dis2[y[i]]+v2[i])sum++;
//		add(x[i],y[i],sum);
	}
	dij(1);
	cout<<dis[n]<<endl;
	return 0;
}