预处理了矩阵的2的幂，但是没用行向量的那个优化，复杂度还是 $O(kn^3\log n)$ 的样子。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
typedef long long ll;
typedef double db;
using namespace std;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=x*10+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const ll INF = 4e18;
int n,m,T,k,c[255];
int N;
struct Mat{ll a[255][255]; Mat(){memset(a,0xc0,sizeof a);}}F,E[31];
inline Mat operator * (const Mat & A,const Mat & B){
    Mat C;
	for(register int i=1;i<=N;++i)
		for(register int k=1;k<=N;++k){
			if(A.a[i][k] < 0)continue;
			for(register int j=1;j<=N;++j){
				C.a[i][j] = max(C.a[i][j],A.a[i][k] + B.a[k][j]);
			}
		}
	return C;
}
void addedge(int u,int v,int w){E[0].a[u][v] = w;}

inline Mat qpow(const Mat & A,int p){ 
	if(p==0)return A;
	Mat ret = A ,B=A;--p;
	for(;p;p>>=1,B=B*B)
		if(p&1)ret=ret*B;
	return ret;
}
struct delicious{
	int t,x,y;
	delicious(){
		t=0,x=0,y=0;
	}
}tt[255];
inline bool cmp(const delicious & a,const delicious & b){
	return a.t < b.t;
}
int id[55][5];

signed main(){
//	freopen("delicacy.in","r",stdin);
//	freopen("delicacy.out","w",stdout);
//	freopen("in.in","r",stdin);
	n=read(),m=read(),T=read(),k=read();
	
	N=n;
	for(register int i=1;i<=n;++i)c[i] = read(),id[i][0] = i;
	for(register int i=1;i<=m;++i){
		int u,v,w;
		u=read(),v=read(),w=read();
		for(register int j=1;j<w;++j) 
			if(!id[u][j]) id[u][j] = ++N,addedge(id[u][j-1],id[u][j],0);
		addedge(id[u][w-1],v,c[v]);
	}
	F.a[1][1] = c[1];
	for(register int i=1;i<=k;++i)tt[i].t=read(),tt[i].x=read(),tt[i].y=read();
	sort(tt + 1,tt + 1 + k,cmp);
	if(tt[k].t != T)tt[++k].t=T;
	
	for(register int i=1;i<=30;++i)E[i] = E[i-1] * E[i-1];
	for(register int i=1;i<=k;++i){
		int t = tt[i].t,x = tt[i].x,y = tt[i].y;
//		F = F*qpow(E,t-tt[i-1].t);
	 	for(register int j=30;j>=0;--j) 
		 	if(t-tt[i-1].t >> j & 1)F = F * E[j];
		for(register int j=1;j<=N;++j)F.a[j][x] += y;  
//		for(register int j=1;j<=N;++j)
//			if(E.a[j][x] > 0)E.a[j][x] += y;  
//		F = F * E;
//		for(register int j=1;j<=N;++j)	
//			if(E.a[j][x] > 0) E.a[j][x] -= y;
	}
//	puts("QAQ");
	if(F.a[1][1] < 0)puts("-1");
	else printf("%lld\n",F.a[1][1] );
	return 0;
}