#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#define VERYBIG (0X7fffffff)
using namespace std;

int n,m;

struct edge
{
	int from;
	int to;
	int ftt_cost;
	int	ttf_cost;
	bool vis;
	edge(int f,int t,int c1,int c2)
	{
		from = f;
		to = t;
		ftt_cost = c1;
		ttf_cost = c2;
	}
};

struct node
{
	vector<edge> ways;
	node()
	{
		ways.clear();
	}
};

node ns[40001];

void read()
{
	cin >> n >> m;
	int u,v,c1,c2;
	int i;
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d %d %d", &u, &v, &c1, &c2);
		ns[u].ways.push_back(edge(u,v,c1,c2));
		ns[v].ways.push_back(edge(v,u,c2,c1));
	}
}

int r = VERYBIG;

void dfs(int n,int w)
{
	if(n == 1 && w != 0)
	{
		r = min(r, w);
		return;
	}else
	{
		int i,j,k,l;
		edge *m;
		for(i = 0; i < ns[n].ways.size(); i++)
		{
			if(!ns[n].ways[i].vis)
			{
				j = ns[n].ways[i].to;
				k = ns[n].ways[i].ftt_cost;
				
				ns[n].ways[i].vis = true;
				for(l = 0; l < ns[j].ways.size(); l++)
				{
					if(ns[j].ways[l].to == n)
					{
						m = &ns[j].ways[l];
						break;
					}
				}
				m->vis = true;
				
				dfs(j,w+k);
				
				m->vis = false;
				ns[n].ways[i].vis = false;
			}
		}
	}
}

int main()
{
	freopen("both.in", "r", stdin);
	freopen("both.out", "w", stdout);
	read();
	dfs(1,0);
	if(r == VERYBIG)r = -1;
	cout << r << endl;
	return 0;
}