#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=4e4+,M=1e5+,K=;

int n,m,mx,hd[N],xnt=,to[M<<],nxt[M<<],w[M<<];

int dis[N],sta[N],top,ans=1e9,bin[K];

bool vis[N],use[M];

priority_queue<pair<int,int> >q;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;

}

void init()

{

  int k=n;while(k)k>>=,mx++;mx--;

  bin[]=;for(int i=;i<=mx;i++)bin[i]=bin[i-]<<;

}

void dj()

{

  memset(vis,,sizeof vis);

  while(q.size())

    {

      int k=q.top().second;q.pop();

      if(vis[k])continue;vis[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(!use[i>>]&&dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        q.push(make_pair(-dis[v],v));

      }

    }

  ans=min(ans,dis[]);

}

int main()

{

  n=rdn(); m=rdn(); init();

  for(int i=,u,v,z1,z2;i<=m;i++)

    {

      u=rdn();v=rdn();z1=rdn();z2=rdn();

      add(u,v,z1);add(v,u,z2);

    }

  for(int i=hd[];i;i=nxt[i])sta[++top]=i;

  for(int i=;i<=mx;i++)

    {

      memset(dis,0x3f,sizeof dis);

      for(int j=;j<=top;j++)

    {

      int k=sta[j];

      if(!(to[k]&bin[i]))

        {

          q.push(make_pair(-w[k],to[k]));use[k>>]=;

          dis[to[k]]=w[k];

        }

    }

      dj();

      memset(dis,0x3f,sizeof dis);

      for(int j=;j<=top;j++)

    {

      int k=sta[j];

      if(to[k]&bin[i])

        {

          q.push(make_pair(-w[k],to[k]));use[k>>]=;

          dis[to[k]]=w[k];

        }

      else use[k>>]=;

    }

      dj();

      for(int j=;j<=top;j++)

    if(to[sta[j]]&bin[i])use[sta[j]>>]=;

    }

  printf("%d\n",ans==1e9?-:ans);

  return ;

}