#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x=0;
	bool flag=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=0;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return (flag?x:~(x-1));
}
struct node{
	int to,nxt,v1,v2;
} edge[200001];
struct que{
	int to,val;
	bool operator<(const que& x)const
	{
		return val>x.val;
	}
};
int n,m,cnt,head[100001],dis[100001],vis[100001];
void add(int a,int b,int c,int d)
{
	edge[++cnt].to=b;
	edge[cnt].v1=c;
	edge[cnt].v2=d;
	edge[cnt].nxt=head[a];
	head[a]=cnt;
}
priority_queue<que> q;
void dij()
{
	for(int i=2;i<=n;i++)
		dis[i]=2e18;
	q.push({1,0});
	while(!q.empty())
	{
		int t=q.top().to;
		q.pop();
		if(vis[t])
			continue;
		vis[t]=1;
		for(int i=head[t];i;i=edge[i].nxt)
		{
			int adj=edge[i].to,minn;
			int qr=sqrt(edge[i].v2);
			if(dis[t]>=qr)
				minn=dis[t]+edge[i].v1+edge[i].v2/(dis[t]+1);
			else
				minn=qr+edge[i].v1+edge[i].v2/(qr+1);
			/*
			for(int l=dis[t];l<=sqrt(edge[i].v2)+5;l++)
				minn=min(minn,l+edge[i].v1+edge[i].v2/(l+1));
			for(int l=max(edge[i].v2/(dis[t]+1),sqrt(edge[i].v2)+1);l>=0;l--)
				minn=min(minn,l+edge[i].v1+edge[i].v2/(l+1));
			*/
			if(minn<dis[adj])
			{
				dis[adj]=minn;
				q.push({adj,minn});
			}
		}
	}
}
signed main()
{
	n=read();
	m=read();
	while(m--)
	{
		int a=read(),b=read(),c=read(),d=read();
		add(a,b,c,d);
		add(b,a,c,d);
	} 
	dij();
	if(dis[n]==2e18)
		puts("-1");
	else
		cout<<dis[n];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m;
int cnt[2];

int main() {
	scanf("%d %d", &n, &m);
	while (n--) {
		char s[30], sum = 0; scanf("%s", s);
		for (int j = 0; j < m; ++j)
			sum ^= s[j] ^ '0';
		++cnt[sum];
	}
	printf("%lld\n", 1ll * cnt[0] * cnt[1]);
	return 0;
}

