#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 100000
#define M 200000
const long long inf=8e18;
using namespace std;
int n,m,u[M+5],v[M+5],c[M+5],p[M+5],tot;
vector<int> color[N+5],id[N+5];
long long sumc[N+M+5];
vector<pair<int,long long> > e[M+N+5]; 
inline void add(int u,int v,long long val) {e[u].push_back({v,val});}
inline int Id(int u,int c) {return id[u][lower_bound(color[u].begin(),color[u].end(),c)-color[u].begin()];}
inline long long dijkstra()
{
	#define y edge.first
	#define w edge.second
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
	static long long f[N+M+5];static bool vis[N+M+5];for(int i=1;i<=tot;++i) f[i]=inf;f[1]=0;q.push({0,1});
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(vis[x]) continue;vis[x]=1;
		if(x==n) return f[x];
		for(pair<int,long long> edge:e[x])
			if(f[y]>f[x]+w) f[y]=f[x]+w,q.push({f[y],y});
	}
	return -1;
	#undef y
	#undef w
}
int main()
{
	scanf("%d %d",&n,&m),tot=n;
	for(int i=1;i<=m;++i)
	{
		scanf("%d %d %d %d",u+i,v+i,c+i,p+i);
		color[u[i]].push_back(c[i]);
		color[v[i]].push_back(c[i]);
	}
	for(int i=1;i<=n;++i)
	{
		sort(color[i].begin(),color[i].end());
		color[i].erase(unique(color[i].begin(),color[i].end()),color[i].end());
		id[i].resize(color[i].size());
		for(unsigned j=0;j<id[i].size();++j) id[i][j]=++tot;
	}
	for(int i=1;i<=m;++i)
	{
		sumc[Id(u[i],c[i])]+=p[i];
		sumc[Id(v[i],c[i])]+=p[i];
	}
	for(int i=1;i<=n;++i) for(int j:id[i]) add(i,j,0);
	for(int i=1;i<=m;++i)
	{
		int uc=Id(u[i],c[i]),vc=Id(v[i],c[i]);
		add(u[i],v[i],p[i]),add(v[i],u[i],p[i]);
		add(u[i],vc,0),add(vc,u[i],sumc[vc]-p[i]);
		add(v[i],uc,0),add(uc,v[i],sumc[uc]-p[i]);
	}
	printf("%lld",dijkstra());
	return 0;
}