#include<bits/stdc++.h>
using namespace std;
#define sz 200005
struct site
{
	int st, stim, ed, etim;
};
site dld[sz];
int n, m, top;
int wei[sz];
bool vis[sz << 1 | 1];
vector<int> tim[sz], ber[sz], fsl[sz << 1 | 1];
int read();
int haf(int, int);
void dfs(int);
int main()
{
	freopen("mooroutetwo.in","r",stdin);
	freopen("mooroutetwo.out","w",stdout);
	int x, y;
	n = read(); m = read();
	for (int i = 1; i <= m; ++i)
	{
		dld[i].st = read();
		dld[i].stim = read();
		dld[i].ed = read();
		dld[i].etim = read();
	}
	for (int i = 1; i <= n; ++i)
		wei[i] = read();
	for (int i = 1; i <= m; ++i)
	{
		tim[dld[i].st].emplace_back(dld[i].stim);
		tim[dld[i].ed].emplace_back(dld[i].etim + wei[dld[i].ed]);
	}
	for (int i = 1; i <= n; ++i)
		if (tim[i].size())
		{
			sort(tim[i].begin(), tim[i].end());
			x = 0;
			for (int j = 1; j < tim[i].size(); ++j)
				if (tim[i][j] != tim[i][x])
					tim[i][++x] = tim[i][j];
			tim[i].resize(x + 1);
			for (int j = 0; j <= x; ++j)
				ber[i].emplace_back(++top);
			for (int j = 1; j <= x; ++j)
				fsl[ber[i][j - 1]].emplace_back(ber[i][j]);
		}
	for (int i = 1; i <= m; ++i)
	{
		x = haf(dld[i].st, dld[i].stim);
		y = haf(dld[i].ed, dld[i].etim + wei[dld[i].ed]);
		fsl[x].emplace_back(y);
	}
	if (ber[1].size())
		dfs(1);
	puts("0");
	for (int i = 2; i <= n; ++i)
	{
		x = 1;
		for (int j = 0; j < ber[i].size(); ++j)
			if (vis[ber[i][j]])
			{
				printf ("%d\n", tim[i][j] - wei[i]);
				x = 0; break;
			}
		if (x)
			puts("-1");
	}
	return 0;
}

int read()
{
	int x = 0;
	char c = getchar();
	while (c < '0') c = getchar();
	do {
		x = x * 10 + (c & 15);
		c = getchar();
	}while (c >= '0');
	return x;
}

int haf(int a, int b)
{
	int lf = 0, rt = tim[a].size(), mid;
	while (rt > lf + 1)
	{
		mid = lf + rt >> 1;
		if (tim[a][mid] <= b)
			lf = mid;
		else
			rt = mid;
	}
	return ber[a][lf];
}

void dfs(int a)
{
	vis[a] = true;
	for (int i : fsl[a])
		if (!vis[i])
			dfs(i);
}