1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MX=1'000'000'000;
const int K=100'000;

int n,m;
int arr[105];
vector<ii> al[205];
vector<ii> alr[205];

bool vis[105][K+5];
int best[105][K+5];

void dfs(int i,int j){
	if (j>min(K,arr[i])) return;
	
	if (vis[i][j]) return;
	vis[i][j]=true;
	
	for (auto [it,w]:al[i]){
		dfs(it,j*w);
	}
}

int mx[105][MX/K+5];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n>>m;
		rep(x,1,n+1) cin>>arr[x];
		rep(x,1,n+1) al[x].clear();
		rep(x,1,n+1) alr[x].clear();
		
		rep(x,1,n+1){
			memset(vis[x],false,sizeof(vis[x]));
			memset(best[x],-1,sizeof(best[x]));
			memset(mx[x],0,sizeof(mx[x]));
		}
		
		rep(x,0,m){
			int a,b,c; cin>>a>>b>>c;
			al[a].pub({b,c});
			alr[b].pub({a,c});
		}
		
		dfs(1,1);
		rep(x,1,n+1){
			rep(y,0,K+1){
				if (vis[x][y]) best[x][y]=y;
				else if (y) best[x][y]=best[x][y-1];
			}
		}
		
		priority_queue<iii,vector<iii> > pq;
		mx[n][1]=arr[n];
		pq.push({mx[n][1],n,1});
		
		while (!pq.empty()){
			int w,a,b; tie(w,a,b)=pq.top(); pq.pop();
			if (w!=mx[a][b]) continue;
			
			for (auto [it,b2]:alr[a]) if (b*b2<=MX/K){
				int mx2=min(w/b2,arr[it]);
				if (mx[it][b*b2]<mx2){
					mx[it][b*b2]=mx2;
					pq.push({mx2,it,b*b2});
				}
			}
		}
		
		int ans=-1;
		
		if (n==1) ans=1;
		
		rep(x,1,n+1) rep(y,1,MX/K+1) for (auto [it,w]:alr[x]){
			int oth=min(mx[x][y]/w,K);
			if (best[it][oth]!=-1) ans=max(ans,best[it][oth]*w*y);
		}
		
		cout<<ans<<endl;
	}
}