#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct node {int x,s;};
int n,m;
int dis[30010],mark[30010];
vector <node> ns[30010];
vector <int> marki[30010];
queue <int> q;
int N;
int father[30010],ans[30010],haha=2100000000;
void clear(int x)
{
   for(int i=1;i<=n;i++)
      dis[i]=1500000000;
   dis[x]=0;
}
void clearmarki()
{
   for(int i=1;i<=n;i++)
      if(marki[i].size())
	     marki[i].clear();
}
int check(int x,int y)
{
   for(int i=0;i<marki[x].size();i++)
   {
      if(marki[x][i]==y)return 1;
   }
   return 0;
}
int SPFA(int x,int y)
{
   clear(x);
   q.push(x);
   mark[x]=1;
   while(!q.empty())
   {
      N=q.front();
	  q.pop();
	  mark[N]=0;
	  for(int i=0;i<ns[N].size();i++)
	  {
	      if(check(N,ns[N][i].x))continue;
	      if(dis[ns[N][i].x]>dis[N]+ns[N][i].s)
		  {
		  	 if(y)father[ns[N][i].x]=N;
		     dis[ns[N][i].x]=dis[N]+ns[N][i].s;
		     if(!mark[ns[N][i].x])
			 {
			     mark[ns[N][i].x]=1;
			     q.push(ns[N][i].x);
			 }
		  }
	  } 
   }
   return 0;
} 
node shit;
void insert(int x,int y,int z)
{
   shit.x=y;
   shit.s=z;
   ns[x].push_back(shit);
}
void search(int x)
{
   if(father[x]==x)return ;
   marki[x].push_back(father[x]);
   marki[father[x]].push_back(x);
   search(father[x]);
   return ;
}
int main()
{
   freopen("zaw.in","r",stdin);
   freopen("zaw.out","w",stdout);
   int x1,x2,x3,x4;
   scanf("%d %d",&n,&m);
   for(int i=1;i<=m;i++)
   {
      scanf("%d %d %d %d",&x1,&x2,&x3,&x4);
      insert(x1,x2,x3);
      insert(x2,x1,x4);
   }
   for(int i=1;i<=n;i++)
      father[i]=i;
   SPFA(1,1);
   for(int i=2;i<=n;i++)ans[i]=dis[i];
   for(int i=2;i<=n;i++)
   {
      if(ans[i]!=1500000000)
	  {
	  	 clearmarki();
	  	 search(i);
	     SPFA(i,0);
	     if(dis[1]==1500000000)continue;
	     haha=min(haha,ans[i]+dis[1]);
	  }
   }
   if(haha!=2100000000)printf("%d",haha);
   else printf("-1");
}