#include <bits/stdc++.h>

using namespace std;
const int N = 2e5+5;
typedef long long ll;
int n, m, idx[N];
ll dis[N], a[N];
struct node {
	int r, d, s;
	bool friend operator < (const node & a, const node & b) {
		return a.r > b.r;
	}
};
vector <node> e[N];
void bfs () {
	queue <int> q; dis[1] = 0; q.push(1);
	while (q.size()) {
		int t = q.front(); q.pop();
		while (idx[t] < (int)e[t].size()) {
			int j = idx[t];
			if (dis[t]+a[t] > e[t][j].r && t > 1) break;
			dis[e[t][j].d] = min(dis[e[t][j].d], (ll)e[t][j].s);
//			cout << e[t][j].d << ' ' << dis[e[t][j].d] << endl;
			q.push(e[t][j].d);
			idx[t]++;
		}
	}
}

int main () {
	freopen("mooroutetwo.in", "r", stdin);
	freopen("mooroutetwo.out", "w", stdout);
	memset(dis, 0x3f, sizeof(dis));
	scanf("%d%d", &n, &m);
	while (m--) {
		node t; int x;
		scanf("%d%d%d%d", &x, &t.r, &t.d, &t.s);
		e[x].push_back(t);
	}
	for (int i = 1;i <= n;i++) {
		scanf("%lld", &a[i]);
		sort (e[i].begin(), e[i].end());
	}
	bfs();
	for (int i = 1;i <= n;i++) {
		if (dis[i] < 0x3f3f3f3f3f3f3f3f) printf("%lld\n", dis[i]);
		else printf("-1\n");
	}
	return 0;
}