#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;
const int SIZEN=30010,INF=0x7fffffff/2;
int N,M;
deque<pair<int,int> > s[SIZEN];
int ma=INF;
void read()
{
	scanf("%d%d",&N,&M);
	int fr,to,c1,c2;
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d%d%d",&fr,&to,&c1,&c2);
		s[fr].push_back(make_pair(to,c1));
		s[to].push_back(make_pair(fr,c2));
	}
}
bool visit[SIZEN]={0};
int st=0;
void dfs(int x,int now)
{
	if(now>ma) return;
	visit[x]=1;
	for(int i=0;i<s[x].size();i++)
	{
		if(x!=st&&s[x][i].first==1)
		{
			if(now+s[x][i].second<ma) ma=now+s[x][i].second;
			continue;
		}
		if(visit[s[x][i].first]) continue;
		dfs(s[x][i].first,now+s[x][i].second);
	}
	visit[x]=0;
}
void work()
{
	for(int i=0;i<s[1].size();i++)
	{
	memset(visit,0,sizeof(visit));
	st=s[1][i].first;
	dfs(s[1][i].first,s[1][i].second);
	}
	if(ma==INF) printf("-1");
	else printf("%d",ma);
}
int main()
{
	freopen("zaw.in","r",stdin);
	freopen("zaw.out","w",stdout);
	read();
	work();
	return 0;
}