由于每条边的到达时间固定，不同走法走到该边起点并不能对让该边产生更优秀的收益，所以每条边只需要走一次即可。

使用DFS来完成搜索，每条边只需要走一次，记录每个点枚举边的起点即可。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
const int N = 200010;
struct node{
	int r, s, v;
	friend bool operator<(const node a, const node b) {
		return a.r > b.r || ( a.r == b.r && a.s < b.s ) ;
	}
};
vector<node>G[N];
int a[N], ans[N], index[N], n, m;
 
void DFS(int x, int t) {
	for(int i = index[x]; i < (int)G[x].size(); i++) {
		int v = G[x][i].v;
		if(t > G[x][i].r)break;
		ans[v] = min(ans[v], G[x][i].s);
		index[x] = i + 1;
		DFS(v, G[x][i].s + a[v]);
	}
	return ;
}
 
int main()
{
	int c, r, d, s;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=m; i++) {
		scanf("%d %d %d %d", &c, &r, &d, &s);
		G[c].push_back((node){r, s, d});
	}
	for(int i=1; i<=n; i++) {
		scanf("%d", &a[i]);
		sort(G[i].begin(), G[i].end());
		ans[i] = 1e9+10;
	}
	ans[1] = 0;
	DFS(1, 0);
	for(int i=1; i<=n; i++) {
		printf("%d\n", ans[i] == 1e9+10 ? -1 : ans[i]);
	}
	return 0;
}