飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1853

大致意思:(我是直接将0~n-1变为1~n)有m回合进化，每次进化有T个要求，就是i中有P（i,j）变为j，求最后n物种的数量，典型的矩阵快速幂的题目，令matrix[i][j]表示第i个物种有多少转化为第j个物种，即P（i,j），A[]为初始状态，则结果矩阵为A*(matrix)^m其中最后一列的和即为答案

//
//  main.cpp
//  zoj2853
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define  LL long long
using namespace  std;
struct Matrix{
    double  mat[234][234];
};
int n,m,k;
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j]);
            }
        }
    }
    return c;
}
Matrix poww(Matrix a,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=n;i++)ans.mat[i][i]=1;
    while(k!=0){
        if(k%2==1){
            ans=MUL(ans,a);
        }
        a=MUL(a,a);
        k/=2;
    }
    return ans;
}
Matrix a;
LL ai[234];
double ci[234];
void init(){
    memset(a.mat,0,sizeof(a.mat));
    for(int i=1;i<=n;i++)scanf("%lld",&ai[i]);
    int t;
    scanf("%d",&t);
    for(int i=1;i<=n;i++)ci[i]=1;
    for(int i=1;i<=t;i++){
        int u,v;
    
        double c;
        scanf("%d%d%lf",&u,&v,&c);
            u++;v++;
        ci[u]-=c;
        a.mat[u][v]+=c;
    }
    for(int i=1;i<=n;i++)a.mat[i][i]=ci[i];
}
double ans;
void play(){
    Matrix c=poww(a,m);
    ans=0;
    for(int i=1;i<=n;i++){
        ans+=ai[i]*c.mat[i][n];
    }
}
void pri(){
    printf("%.0f\n",ans);
}
int main() {
    // insert code here...
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)break;
        init();
        play();
        pri();
    }
    return 0;
}