#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
struct N{
	int to,dist;
};
vector<N> p1[40010];
vector<N> p2[40010];
vector<int> p[40010];
bool vis[100100];
int m,n;
int dis1[40010];
int dis2[40010];
void spfa1()
{
	queue<int>q;
	memset(vis,0,sizeof(vis));
	memset(dis1,-1,sizeof(dis1));
	q.push(1);
	dis1[1]=0;
	while (!q.empty())
	{
		int k=q.front();
		vis[k]=false;
		q.pop();
		if (p1[k].size()>0)
		{
			for (int i=0;i<p1[k].size();i++)
			{
				N&e=p1[k][i];
				if (dis1[e.to]==-1||dis1[e.to]>dis1[k]+e.dist)
				{
					dis1[e.to]=dis1[k]+e.dist;
					if (!vis[e.to])
					{
						vis[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
	}
}
void spfa2()
{
	queue<int>q;
	memset(vis,0,sizeof(vis));
	memset(dis2,-1,sizeof(dis2));
	q.push(1);
	dis2[1]=0;
	while (!q.empty())
	{
		int k=q.front();
		vis[k]=false;
		q.pop();
		if (p2[k].size()>0)
		{
			for (int i=0;i<p2[k].size();i++)
			{
				N&e=p2[k][i];
				if (dis2[e.to]==-1||dis2[e.to]>dis2[k]+e.dist)
				{
					dis2[e.to]=dis2[k]+e.dist;
					if (!vis[e.to])
					{
						vis[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
	}
}
int main()
{
	freopen("both.in","r",stdin);
	freopen("both.out","w",stdout);
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int u,v,c1,c2;
		cin>>u>>v>>c1>>c2;
		p1[u].push_back((N){v,c1});
		p2[u].push_back((N){v,c2});
	}
	spfa1();
	spfa2();
	int v=1;
	int ans=100000000;

    cout<<-1;
    return 0;
}