#include<iostream>
#include<vector>
#include<set>
#include<unordered_map>
#include<algorithm>
#include<queue>
#include<math.h>

using namespace std;

struct Edge;
struct Node;

queue<pair<int, long long> > toVisitFwd;
queue<pair<int, pair<long long, long long> > > toVisitBck;

//long long EXP = 437838128LL;

long long MAX = 40000LL;

struct Edge {
	Node* start;
	Node* end;
	long long multiplier;
};

struct Node {
	int index;
	vector<Edge*> in;
	vector<Edge*> out;
	long long p;
	vector<long long> possibleMultsFwd;
	set<long long> visitedMultsFwd;
	
	priority_queue<long long> multsBckPrq;
	// map from multiplier to the limit
	unordered_map<long long, long long> multsBck;
	
	void visitForward(long long m) {
		if (p < m) {
			return;
		}
		
		if (visitedMultsFwd.find(m) != visitedMultsFwd.end()) {
			return;
		}
				
		visitedMultsFwd.insert(m);
		possibleMultsFwd.push_back(m);
		
		for (Edge* edge : out) {
			if ((MAX >= m || edge->multiplier == 1LL)) {
				toVisitFwd.push(make_pair(edge->end->index, m * (edge->multiplier)));
			}
		}
	}

	void visitBackward(long long m, long long limit) {
		if (limit == 0LL) {
			return;
		}
		
		if (limit >= p) {
			limit = p;
		}
		
		if (multsBck.find(m) != multsBck.end()) {
			long long oldLimit = multsBck[m];
			if (limit <= oldLimit) {
				return;
			}
		}
		
		multsBck[m] = limit;
		multsBckPrq.push(m);

		
		if (MAX >= m) {
			for (Edge* edge : in) {
				toVisitBck.push(make_pair(edge->start->index, make_pair(m * (edge->multiplier), limit / (edge->multiplier))));
			}
		}
		
	}
	
	long long calculateMax() {
		if (possibleMultsFwd.size() == 0) {
			return -1LL;
		}
		
		sort(possibleMultsFwd.begin(), possibleMultsFwd.end());
		
		vector<pair<long long, long long> > multsAndLimits;
		
		long long currentLimit = -100LL;
		
		
		while (!multsBckPrq.empty()) {
			long long mult = multsBckPrq.top();
			multsBckPrq.pop();
			if (multsBck.find(mult) == multsBck.end()) {
				continue;
			}
			long long limit = multsBck[mult];
			
			if (limit > currentLimit) {
				multsAndLimits.push_back(make_pair(mult, limit));
				currentLimit = limit;
			}
		}
		
		long long mx = -1LL;
		int im = 0;
						
		for (int i = 0; i < multsAndLimits.size(); i++) {
			long long  limit = multsAndLimits[i].second;
			long long mult = multsAndLimits[i].first;
			
			while (im < possibleMultsFwd.size() - 1 && possibleMultsFwd[im + 1] <= limit) {
				im++;
			}
			
			
			long long forwMult = possibleMultsFwd[im];
			long long curr = mult * forwMult;
			
			if (forwMult > limit) {
				continue;
			}
			

			
			if (mx < curr) {
				mx = curr;
			}
		}
		
		return mx;
	}
};

long long singleRun() {
	int n, m;
	cin >> n >> m;
	
	vector<Node*> nodes(n + 1);
	
	for (int i = 1; i <= n; i++) {
		long long p;
		cin >> p;
		Node* node = new Node();
		node->index = i;
		node->p = p;
		nodes[i] = node;
	}
	
	MAX = (long long) sqrt(nodes[n]->p) + 10LL;
	
	for (int i = 0; i < m; i++) {
		int a, b;
		long long w;
		cin >> a >> b >> w;
		Edge* edge = new Edge();
		edge->start = nodes[a];
		edge->end = nodes[b];
		edge->multiplier = w;
		nodes[a]->out.push_back(edge);
		nodes[b]->in.push_back(edge);
	}
	
	toVisitFwd.push(make_pair(1, 1LL));
	
	while (!toVisitFwd.empty()) {
		pair<int, long long> fr = toVisitFwd.front();
		toVisitFwd.pop();
		
		nodes[fr.first]->visitForward(fr.second);
	}
	
	toVisitBck.push(make_pair(n, make_pair(1, nodes[n]->p)));
	
	while (!toVisitBck.empty()) {
		pair<int, pair<long long, long long> > fr = toVisitBck.front();
		toVisitBck.pop();
		nodes[fr.first]->visitBackward(fr.second.first, fr.second.second);
	}

	long long mx = -1LL;
	for (int i = 1; i <= n; i++) {
		long long current = nodes[i]->calculateMax();
		if (mx < current) {
			mx = current;
		}
	}
	
	return mx;
}

int main() {
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	
	int T;
	cin >> T;
	vector<long long> results(T);
	for (int i = 0; i < T; i++) {
		results[i] = singleRun();
	}
	
	for (int i = 0; i < T; i++) {
		cout << results[i] << "\n";
	}
	
}