#include <bits/stdc++.h>
using namespace std;
const int SIZE=1e2+2;
vector<pair<int,long long>> graph[SIZE];
long long P[SIZE];
set<int> S[SIZE];
int MAX,N;

void DFS(int v,long long w){
    if(w>P[v]||w>P[N]){return;}
    if(S[v].find(w)!=S[v].end()){return;}

    if(v==N){MAX=max(MAX,(int)w);}
    S[v].insert(w);

    for(auto u:graph[v]){
        DFS(u.first,w*u.second);
    }
}

void CLEAR(){
    for(int i=0;i<SIZE;i++){graph[i]={};}
    for(int i=0;i<SIZE;i++){P[i]=0;}
    for(int i=0;i<SIZE;i++){S[i].clear();}
    MAX=-1;
}

int main(){
    int T,M,a,b,c;

    cin>>T;

    for(int t=1;t<=T;t++){

    CLEAR();
    cin>>N>>M;

    for(int i=1;i<=N;i++){cin>>P[i];}
    for(int i=0;i<M;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
    }
    DFS(1,1);

    cout<<MAX<<'\n';

    }

return 0;}