#include<stdio.h>
#include<queue>
#include<iostream>
#include<vector>
#include<algorithm>
#define maxn 40050
#define inf 1e+9
using namespace std;
typedef pair<int,int> pi;
int n,m,ans=inf;
int dis[maxn],dis2[maxn];
bool use[maxn],vis[maxn];
struct node{
	vector<int> ne;
	vector<int> v;
	vector<bool> cantuse;
}ns[maxn];
void beg(){
	for(int i=1;i<=maxn;i++){
		dis[i]=inf;
		use[i]=false;
	}
}
void read(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,xy,yx;
		scanf("%d %d %d %d",&x,&y,&xy,&yx);
		ns[x].ne.push_back(y);
		ns[x].v.push_back(xy);
		ns[x].cantuse.push_back(false);
		ns[y].ne.push_back(x);
		ns[y].v.push_back(yx);
		ns[y].cantuse.push_back(false);
	}
}
int dijkstra(int be,int en){
	beg();
	priority_queue< pi , vector< pi > , greater< pi > > q;
	dis[be]=0;
	q.push(make_pair(0,be));
	while(!q.empty()){
		int tmp=q.top().second,distmp=q.top().first;
		q.pop();
		if(tmp==en) return dis[en];
		use[tmp]=true;
		for(int i=0;i<ns[tmp].ne.size();i++){
			int j=ns[tmp].ne[i];
			if(ns[tmp].cantuse[i])continue;
			if(dis[j]>distmp+ns[tmp].v[i]){
				dis[j]=distmp+ns[tmp].v[i];
				if(!use[j])q.push(make_pair(dis[j],j));
			}
		}
	}
	return dis[en];
}
int dfs(int x){
	for(int i=0;i<ns[x].ne.size();i++){
		int tmp=ns[x].ne[i];
		if(vis[tmp])continue;
		ns[tmp].cantuse[i]=true;
		dis2[tmp]+=dis2[x]+ns[x].v[i];
		vis[tmp]=true;
		ans=min(ans,dis2[tmp]+dijkstra(tmp,1));
		dfs(tmp);
		vis[tmp]=false;
		dis2[tmp]-=dis2[x]+ns[x].v[i];
		ns[tmp].cantuse[i]=false;
	}
	return ans==inf ? -1:ans;
}
int solve(){
	for(int i=1;i<=n;i++){
		for(int j=0;j<ns[i].ne.size();j++){
	//		printf("%d->%d: dij:%d w:%d\n",i,ns[i].ne[j],dijkstra(i,ns[i].ne[j]),ns[i].v[j]);
			ans=min(ans,dijkstra(ns[i].ne[j],i)+ns[i].v[j]);
		}
	}

}
int main(){
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	read();
	vis[1]=true;
	printf("%d",dfs(1));
	return 0;
}