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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)


#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int


#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; }
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; }
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}


#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue


#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));


using namespace std;

int n;
int p[105];
vector<PII> out[105];
map<PII, int> dp;

int rob(int v, int lim) {
	if (dp.find({v,lim}) != dp.end()) {
		//cout << v <<"," << lim <<": " << dp[{v,lim}] << endl;;
		return dp[{v,lim}];
	}
	if (lim < 1) return -1;
	if (v == 0 && lim == 1) return 1; 
	int best = (v == 0 ? 1 : -1);
	
	VI jedynki;
	set<int> bylo;
	FORE(i, out[v]) {
		int u = i->nd;
		int mnoz = -i->st;

		int limit = min(p[u], lim/mnoz);
		if (limit == lim) {
			if (u == 0) best = max(best, 1);
			jedynki.pb(u);
		}	
		else {
			best = max(best, rob(u, limit)*mnoz);
		}
	}
	bylo.insert(v);
	for (int i = 0; i < jedynki.size(); i++) {
		int w = jedynki[i];
		if (bylo.find(w) != bylo.end()) continue;
		bylo.insert(w);
		FORE(j, out[w]) {
			int u = j->nd;
			int mnoz = -j->st;

			int limit = min(p[u], lim/mnoz);
			if (limit == lim) {
				if (u == 0) best = max(best, 1);
				if (bylo.find(u) == bylo.end()) jedynki.pb(u);
			} else {
				best = max(best, rob(u, limit)*mnoz);
			}
		}
	}

	dp[{v,lim}]=best;
	//	cout << v <<"," << lim <<": " << dp[{v,lim}] << endl;;
	return best;
}

void solve() {
	read(n); make(m);
	FOR(i,0,n) {
		make(a); p[i] = a;
		out[i].clear();
	}
	dp.clear();
	FOR(i,0,m) {
		make3(a,b,w); a--; b--;
		if (a == b && w == 1) continue;
		if (w > p[b] || w > p[n-1]) continue;
		out[b].pb({-w,a});
	}
	FOR(i,0,n) {
		sort(out[i].begin(), out[i].end());
		out[i].erase( unique( out[i].begin(), out[i].end() ), out[i].end() );
		/*cout << "OUT " << i << ": ";
		FOR(j,0,out[i].size()) {
			cout << out[i][j].st << "," <<out[i][j].nd <<"  ";
		}
		cout << endl; */
	}

	printf("%d\n", rob(n-1,p[n-1]));
}


int main() {
	make(z);
	while (z--) {
		solve();
	}
}