// KZ's
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("both.in");
ofstream fout ("both.out");
///////
#define XXX 40004
///////
class poi {
public:
	int x,v;
	poi push(int a,int b) {
		x=a;
		v=b;
		return *this;
	}
};
///////
vector <poi> mp[XXX];
vector <int> fed[XXX];
bool lsd[XXX]={0,1};
int n,m;
///////
void rin() {
	fin>>n>>m;
	int a,b,c,d;
	poi poiu;
	for (int i=0;i<m;i++) {
		fin>>a>>b>>c>>d;
		mp[a].push_back(poiu.push(b,c));
		mp[b].push_back(poiu.push(a,d));
	}
}
void spfa(int x) {
	vector <int> sed(XXX,0x7fffffff);
	sed[x]=0;
	queue <int> ls;
	ls.push(x);
	lsd[x]=true;
	int u;
	while (!ls.empty()) {
		u=ls.front();
		ls.pop();
		lsd[u]=false;
		for (int i=0;i<mp[u].size();i++) {
			if (sed[u]+mp[u][i].v<sed[mp[u][i].x]) {
				sed[mp[u][i].x]=sed[u]+mp[u][i].v;
				if (!lsd[mp[u][i].x]) {
					ls.push(mp[u][i].x);
					lsd[mp[u][i].x]=true;
				}
			}
		}
	}
	swap(fed[x],sed);
	
}
inline int vvv(poi x,poi y) {
	if (fed[x.x][y.x]==0x7fffffff)
		return -1;
	else
		for (int i=0;i<mp[y.x].size();i++)
			if (mp[y.x][i].x==1)
				return x.v+fed[x.x][y.x]+mp[y.x][i].v;
}
void work() {
	int ed=0x7fffffff;
	int a,b;
	for (int i=0;i<mp[1].size();i++)
		spfa(mp[1][i].x);
	for (int i=0;i<mp[1].size();i++)
		for (int j=i+1;j<mp[1].size();j++) {
			a=vvv(mp[1][i], mp[1][j]);
			if (a>0&&a<ed)
				ed=a;
			a=vvv(mp[1][j], mp[1][i]);
			if (a>0&&a<ed)
				ed=a;
		}
	if (ed==0x7fffffff)
		fout<<-1<<endl;
	else
		fout<<ed<<endl;
}
/////////
int main() {
	rin();
	work();
	return 0;
}
// UBWH