#include<bits/stdc++.h>
using namespace std;
struct edge{ int to,costa,costb; };

int N,P;
vector<edge> G[1000];
vector<int> rG[1000];
map<int,bool> visited;
vector<int> vd;

int d[1000][1000];

void dfs(int pos){
  if(visited[pos])return;
  visited[pos]=true;
  
  for(int i=0;i<(int)rG[pos].size();i++){
    dfs(rG[pos][i]);
  }
  vd.push_back(pos);
}

int main(){
  cin>>N>>P;
  for(int i=0;i<P;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--,b--;
    G[a].push_back( (edge){b,c,d} );
    rG[b].push_back(a);
  }
  
  dfs(N-1);

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      d[i][j]=1e9;
    }
  }

  map<int,int> mp;
  for(int i=0;i<N;i++){
    mp[ vd[i] ]=i;
  }
  
  d[0][0]=0;

  for(int i=0;i<N;i++){
    for(int j=i;j<N;j++){
      int posa=vd[i];
      int posb=vd[j];
      if(i==j){
        for(int k=0;k<(int)G[posa].size();k++){
          for(int l=0;l<=k;l++){
            edge ea=G[posa][k];
            edge eb=G[posb][l];
            
            int toa=mp[ea.to];
            int tob=mp[eb.to];
            int ncost=d[i][j];
            if(toa==tob)ncost+=ea.costa+eb.costb;
            else ncost+=ea.costa+eb.costa;

            if(toa>tob)swap(toa,tob);
            if(d[toa][tob]>ncost){
              d[toa][tob]=ncost;            
            }
          }
        }
        continue;
      }
      for(int k=0;k<(int)G[posa].size();k++){
        edge e=G[posa][k];
        int ncost=d[i][j]+e.costa;
        int to=mp[ e.to ];
        int nb=mp[posb];
        
        if(to>nb)swap(to,nb);
        if(d[to][nb]>ncost){
          d[to][nb]=ncost;
        }
        
      }
    }
  }
  cout<<d[N-1][N-1]<<endl;
  return 0;
}