没人发题解，我发一个

———————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————(防偷窥线)

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}

const int MAXN = 50, MAXM = 501, MAXW = 5, MAXK = 200;
const int LOGT = 29;
const int MT_SIZE = MAXN*5;
const ll LL_INF = 1e18;

struct Matrix{
	ll a[MT_SIZE+5][MT_SIZE+5];
	int size;
	void identity() {
		for(int i=1;i<=size;++i) {
			for(int j=1;j<=size;++j){
				a[i][j] = (i==j ? 0 : -LL_INF);
			}
		}
	}
	Matrix(){
		for(int i=1;i<=MT_SIZE;++i)
			for(int j=1;j<=MT_SIZE;++j)
				a[i][j] = -LL_INF;
		size=0;
	}
};
Matrix operator * (const Matrix& A, const Matrix& B) {
	Matrix C;
	assert(A.size==B.size);
	C.size = A.size;
	for(int i=1;i<=A.size;++i){
		for(int j=1;j<=A.size;++j){
			for(int k=1;k<=A.size;++k){
				if(A.a[i][k] == -LL_INF || B.a[k][j] == -LL_INF)
					continue;
				ckmax(C.a[i][j], A.a[i][k]+B.a[k][j]);
			}
		}
	}
	return C;
}
Matrix mat_pow(Matrix X,int i) {
	Matrix Y;
	Y.size = X.size;
	Y.identity();
	while(i){
		if(i&1)
			Y=Y*X;
		X=X*X;
		i>>=1;
	}
	return Y;
}

int n,m,T,K,c[MAXN+5];
int id[MAXN+5][MAXW+5],cnt_id;

struct Event{
	int t,u,w;
	bool operator < (const Event& rhs) const {
		return t < rhs.t;
	}
}ev[MAXK+5];

Matrix trans,pow_of_trans[LOGT+1];
void init_pow_of_trans() {
	pow_of_trans[0] = trans;
	for(int i=1; i<=LOGT; ++i) {
		pow_of_trans[i] = pow_of_trans[i-1] * pow_of_trans[i-1];
	}
}
void mul_pow_of_trans(Matrix& A, int mi) {
	for(int bit=0; bit<=LOGT; ++bit) {
		if((mi>>bit) & 1) {
			Matrix res;
			res.size=A.size;
			for(int j=1; j<=A.size; ++j) {
				for(int k=1; k<=A.size; ++k) {
					if(A.a[1][k] == -LL_INF || pow_of_trans[bit].a[k][j] == -LL_INF)
						continue;
					ckmax(res.a[1][j], A.a[1][k] + pow_of_trans[bit].a[k][j]);
				}
			}
			A = res;
		}
	}
}

int main() {
	cin >> n >> m >> T >> K;
	for(int i=1;i<=n;++i) {
		cin >> c[i];
	}
	trans.size = n*5;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=5;++j) {
			id[i][j] = ++cnt_id;
		}
		for(int j=1;j<5;++j) {
			trans.a[id[i][j]][id[i][j+1]] = 0;
		}
	}
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin >> u >> v >> w;
		trans.a[id[u][w]][id[v][1]]=c[v];
	}
	for(int i=1; i<=K; ++i) {
		cin >> ev[i].t >> ev[i].u >> ev[i].w;
	}
	sort(ev+1, ev+K+1);
	
	Matrix A;
	A.size = n*5;
	A.a[1][id[1][1]] = c[1];
	init_pow_of_trans();
	
	int last_time = 0;
	for(int i=1; i<=K; ++i) {
		mul_pow_of_trans(A, ev[i].t - last_time);
		if(A.a[1][id[ev[i].u][1]] != -LL_INF) {
			A.a[1][id[ev[i].u][1]] += ev[i].w;
		}
		last_time = ev[i].t;
	}
	if(last_time != T) {
		mul_pow_of_trans(A, T - last_time);
	}
	if(A.a[1][id[1][1]] == -LL_INF)
		cout << -1 << endl;
	else
		cout << A.a[1][id[1][1]] << endl;
	return 0;
}