#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int hd[N],nxt[N],to[N],a[N],b[N],num=1;
void add(int u,int v,int va,int vb) {
	num++;
	to[num]=v;
	a[num]=va;
	b[num]=vb;
	nxt[num]=hd[u];
	hd[u]=num;
}
int n,m;
int ans=0x7f7f7f7f;
bool vis[N];
void dfs(int u,int va,int vb){
    if(u==n){
        ans=min(ans,va+vb);
        return;
    }
    for(int i=hd[u];i;i=nxt[i]){
        if(vis[i]) continue;
        int v=to[i];
        vis[i]=1;
        dfs(v,max(va,a[i]),max(vb,b[i]));
        vis[i]=0;
    }
}
int main(){
    freopen("magicalforest.in","r",stdin);
    freopen("magicalforest.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,va,vb;
        cin>>u>>v>>va>>vb;
        add(u,v,va,vb);
        add(v,u,va,vb);
    }
    dfs(1,0,0);
    cout<<ans;
    return 0;
}