#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=1e5;
const long long Inf=1e18;
int n,m,Num,lin[Max_N+5];
long long sum[Max_M+5];
map<int,long long> dis[Max_N+5],vis[Max_N+5];
struct Edge_fir{ int u,v,c,p; } E[Max_M+5];
vector<int> a[Max_N+5];
priority_queue< pair< long long, pair<int,int> > > Q;
struct Edge{
	int Next,Id,c;
	long long val;
} e[Max_M*4+5];
void Insert(int x,int y,int c,long long w){
	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y; e[Num].c=c; e[Num].val=w;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].c,&E[i].p);
		a[E[i].u].push_back(i),a[E[i].v].push_back(i);
	}
	for(int x=1;x<=n;x++){
		dis[x][-1]=Inf;
		for(int i=0;i<a[x].size();i++)
		 sum[E[a[x][i]].c]+=E[a[x][i]].p,
		 dis[x==E[a[x][i]].u?E[a[x][i]].v:E[a[x][i]].u][a[x][i]]=Inf;
		for(int i=0;i<a[x].size();i++)
		 Insert(x,x==E[a[x][i]].u?E[a[x][i]].v:E[a[x][i]].u,a[x][i],E[a[x][i]].p),
		 Insert(x,x==E[a[x][i]].u?E[a[x][i]].v:E[a[x][i]].u,-1,sum[E[a[x][i]].c]-E[a[x][i]].p);
		for(int i=0;i<a[x].size();i++)
		 sum[E[a[x][i]].c]-=E[a[x][i]].p;
	} 
	Q.push(make_pair(0,make_pair(1,-1)));
	dis[1][-1]=0;
	for(;Q.size();){
		int x=Q.top().second.first;
		int c=Q.top().second.second; Q.pop();
		if(vis[x][c]) continue; vis[x][c]=1;
		for(int i=lin[x];i;i=e[i].Next){
			if(c!=-1&&e[i].c!=-1&&E[c].c==E[e[i].c].c)
			 dis[e[i].Id][e[i].c]=min(dis[e[i].Id][e[i].c],dis[x][c]+e[i].val-E[c].p);
			else dis[e[i].Id][e[i].c]=min(dis[e[i].Id][e[i].c],dis[x][c]+e[i].val);
			Q.push(make_pair(-dis[e[i].Id][e[i].c],make_pair(e[i].Id,e[i].c)));
		}
	}
	long long ans=dis[n][-1];
	for(int i=lin[n];i;i=e[i].Next)
	 ans=min(ans,dis[n][e[i].c]);
	printf("%lld\n",ans);
	return 0;
}