#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 500005
using namespace std;
int n,m,h[N],tot,v[N],idx;long long d[N],c[N<<1];map<int,int>u[N];
struct edge{int to,nxt;long long val;}e[N<<2];
void add(int x,int y,long long z){e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;e[tot].val=z;}
struct node{int y,c,p;};vector<node>a[N];
priority_queue<pair<long long,int> >q;
void dij(){
memset(d,0x3f,sizeof(d));d[1]=0;q.push(make_pair(0,1));
while(!q.empty()){
int x=q.top().second;q.pop();v[x]=1;
for(int i=h[x];i;i=e[i].nxt)if(d[x]+e[i].val<d[e[i].to])
d[e[i].to]=d[x]+e[i].val,q.push(make_pair(-d[e[i].to],e[i].to));
while(!q.empty()&&v[q.top().second])q.pop();
}
}
int main(){
cin>>n>>m;
idx=n;
rep(i,1,m){
int x,y,z,w;scanf("%d%d%d%d",&x,&y,&z,&w);
node cur;cur.y=y;cur.c=z;cur.p=w;
a[x].push_back(cur);cur.y=x;a[y].push_back(cur);
}
rep(x,1,n){
for(int i=0;i<(int)a[x].size();i++)if(!c[a[x][i].c])u[x][a[x][i].c]=++idx,c[a[x][i].c]=1;
for(int i=0;i<(int)a[x].size();i++)c[a[x][i].c]=0;
}
rep(x,1,n){
for(int i=0;i<(int)a[x].size();i++)c[a[x][i].c]+=a[x][i].p;
for(int i=0;i<(int)a[x].size();i++){
add(x,a[x][i].y,a[x][i].p);
add(x,a[x][i].y,c[a[x][i].c]-a[x][i].p);
add(u[x][a[x][i].c],a[x][i].y,c[a[x][i].c]-a[x][i].p);
add(x,u[a[x][i].y][a[x][i].c],0);
}
for(int i=0;i<(int)a[x].size();i++)c[a[x][i].c]=0;
}
dij();
cout<<d[n];
return 0;
}
