评测时分数在85~90之间浮动，最后一个点一直过不了，其他点多多少少都过过一遍。然后，复杂度应该是没有问题的，分段预处理矩阵快速幂。然后，试图卡常无果/kel

#define max(a,b) (a>b?a:b)
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,T,K,c[255];
int nam;
const long long inf=-1e12;
long long E[255][255][50],ans[255],pre[255];
struct node{
    int t,x,y;
    friend bool operator<(node a,node b){
        return a.t<b.t;
    }
}cts[255];
int mk(int a,int b){
    return (a-1)*n+b;
}
void Pub(int val){
    int cur=0;
    while(val){
        if(val&1){
            for(int i=1;i<=nam;i++){
                pre[i]=ans[i];
                ans[i]=inf;
            }
            for(int i=1;i<=nam;i++)
                for(int j=1;j<=nam;j++)
                    if(pre[j]>=0&&E[i][j][cur]>=0)
                    ans[i]=max(ans[i],pre[j]+E[i][j][cur]);
        }
        cur++;
        val>>=1;
    }
}
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin>>n>>m>>T>>K;
    scanf("%d%d%d%d",&n,&m,&T,&K);
    nam=n*5;
    for(int i=1;i<=nam;i++)
        ans[i]=inf;
    for(int i=1;i<=nam;i++)
        for(int j=1;j<=nam;j++)
            E[i][j][0]=inf;
    for(int i=1;i<=n;i++){
        // cin>>c[i];
        scanf("%d",&c[i]);
    }
    for(int i=1,u,v,w;i<=m;i++){
        // cin>>u>>v>>w;
        scanf("%d%d%d",&u,&v,&w);
        E[mk(1,v)][mk(w,u)][0]=c[v];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<5;j++)
            E[mk(j+1,i)][mk(j,i)][0]=0;
    for(int x=1;x<=30;x++){
        for(int i=1;i<=nam;i++)
            for(int j=1;j<=nam;j++){
                E[i][j][x]=inf;
                for(int k=1;k<=nam;k++)
                if(E[i][k][x-1]>=0&&E[k][j][x-1]>=0)
                    E[i][j][x]=max(E[i][j][x],E[i][k][x-1]+E[k][j][x-1]);
            }
    }
    ans[1]=c[1];
    cts[K+1].t=T;
    for(int i=1;i<=K;i++)
        // cin>>cts[i].t>>cts[i].x>>cts[i].y;
        scanf("%d%d%d",&cts[i].t,&cts[i].x,&cts[i].y);
    sort(cts+1,cts+K+1);
    for(int i=1;i<=K+1;i++){
        Pub(cts[i].t-cts[i-1].t);
        ans[cts[i].x]+=cts[i].y;
    }
    if(ans[1]<0)
        // cout<<-1;
        printf("-1");
    // else cout<<ans[1];
    else printf("%lld",ans[1]);
}