#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define N 30050
#define M 100500
#define inf 2000000000
using namespace std;
int n,m,d[N],p[N],dist[N];
bool vis[N],vise[M];
struct Edge{
	int from,to,dist;
};
vector<Edge> edges;
vector<int> g[N];
struct node{
	int x,d;
	bool operator < (const node& rhs)const{
		return d>rhs.d;
	}
};
priority_queue<node> que;
set<int> f[N];
void add(int u,int v,int w)
{
	edges.push_back((Edge){u,v,w});
	g[u].push_back(edges.size()-1);
}
void input()
{
	scanf("%d%d",&n,&m);
	int u,v,w1,w2;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&w1,&w2);
		add(u,v,w1);
		add(v,u,w2);
	}
}
void init()
{
	memset(vis,false,sizeof(vis));
	for(int i=0;i<=n;i++)
	  d[i]=inf;
	memset(vise,false,sizeof(vise));
}
void djs(int t)
{
	init();
	int x=t;
	while(x!=1)
	{
		int o=p[x];
		vise[o^1]=vise[o]=true;
		x=edges[o].from;
	}
	d[t]=0;
	que.push((node){t,0});
	while(!que.empty())
	{
		node x=que.top();
		que.pop();
		int u=x.x;
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=0;i<g[u].size();i++)
		{
			if(vise[g[u][i]]) continue;
			Edge& e=edges[g[u][i]];
			if(d[e.to]>d[u]+e.dist)
			{
				d[e.to]=d[u]+e.dist;
				p[e.to]=g[u][i];
				que.push((node){e.to,d[e.to]});
			}
		}
	}
}
int main()
{
	freopen("zaw.in","r",stdin);
	freopen("zaw.out","w",stdout);
	int ans=inf;
	input();
	djs(1);
	for(int i=2;i<=n;i++)
	{
	  dist[i]=d[i];
	  djs(i);
	  ans=min(dist[i]+d[1],ans);
	}
	if(ans>=inf)
	  printf("-1\n");
	else
	  printf("%d\n",ans);
	return 0;
}