#include<bits/stdc++.h>
using namespace std;
const int N=500005;
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;
for(int i=1;i<=m;i++)
{
int x,y,z,w;
cin>>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);
}
for(int x=1;x<=n;x++)
{
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;
}
for(int x=1;x<=n;x++)
{
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;
}
