#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define MAX 9999999
using namespace std;
int n,m,x,y,z,ans=MAX;;
int map[1005][1005],dist[1005][1005];
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	cin>>n>>m;
	if(n<=1000)
	{
	for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		  {
				map[i][j]=map[j][i]=-1;
				dist[i][j]=dist[j][i]=MAX;		  
		  }
	for(int i=1;i<=m;i++)
	{
		int u,v,c1,c2;
		cin>>u>>v>>c1>>c2;
		map[u][v]=dist[u][v]=c1;
		map[v][u]=dist[v][u]=c2;
	}
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		     if(i!=j&&j!=k&&i!=k) 
			    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	int k=1;
	for(int i=n;i>k;i--)
	   for(int j=i-1;j>k;j--)
	   {
	   	if((map[i][k]==-1||map[k][j]==-1)&&(map[k][i]==-1||map[j][k]==-1)) continue;
	   	if((map[i][k]!=-1&&map[k][j]!=-1)&&(map[k][i]==-1||map[j][k]==-1))
	   	   ans=min(ans,dist[j][i]+map[i][k]+map[k][j]);
	   	if((map[k][i]!=-1&&map[j][k]!=-1)&&(map[i][k]==-1||map[k][j]==-1))
	   	   ans=min(ans,dist[i][j]+map[k][i]+map[j][k]);
	   	if((map[i][k]!=-1&&map[k][j]!=-1)&&(map[k][i]!=-1&&map[j][k]!=-1))
	   	   ans=min(ans,min(dist[j][i]+map[i][k]+map[k][j],dist[i][j]+map[k][i]+map[j][k]));
	   }
	 if(ans!=MAX)cout<<ans<<endl;
	    else cout<<"-1"<<endl;
	}
	else cout<<"-1"<<endl;
}