#include <iostream>


//ZASTĄP KRAWĘDZIE O WADZE 1 PRZEZ 
//TABLICE MINIMALNEGO OGRANICZENIA POTRZEBNEGO DO PRZEJŚCIA OD WIERZCHOŁKA a DO b STOSUJĄC TYLKO JEDYNKI. 

//TABLICE STOSUJ DO BEZPOŚREDNIEGO PRZEJŚCIA POMIĘDZY WIERZCHOŁKI. 




//ZLICZAJ ŚCIEŻKI OD START  (GDZIE KONIEC I JAKA MOC).
//KONIEC MUSI MIEĆ MOC CONAJWYŻEJ (p_n)^(2/3).

//UWAGA : USUWAJ DUPLIKATY

//ZLICZAJ ŚCIEŻKI DO END, (GDZIE POCZĄTEK, JAKI MNOŻNIK I JAKIE OGRANICZENIE).
//MNOŻNIK MUSI BYĆ CONAJMNIEJ (p_n)^(1/3).

//UWAGA : PRZY USUWANIU DUPLIKATÓW ZOSTAW TO Z WIĘKSZYM OGRANICZENIEM.

//PODCZAS ZLICZANIA SORTUJ KRAWĘDZIE WEDLUG WAG, ABY SPRAWDZAĆ TYLKO DOBRE KRAWĘDZIE


//NA KONIEC DLA KAŻDEGO WIERZCHOŁKA I KAŻDEJ ŚCIEŻKI OD NIEGO DO END 
//ZNAJDŹ NAJWIĘKSZY MNOŻNIK MNIEJSZY OD OGRANICZENIA SPOŚRÓD ŚCIEŻEK OD START DO WIERZCHOŁKA

#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>

const int MAX_N = 100;
std::vector<std::pair<int, long long>> graph[MAX_N];
std::vector<std::pair<int, long long>> rev_graph[MAX_N];

long long przep[MAX_N];
long long transitions[MAX_N][MAX_N];
bool visited[MAX_N];
std::vector<std::pair<int, long long>> trans_vec[MAX_N];
std::vector<std::pair<int, long long>> rev_trans_vec[MAX_N];
struct Start_frag {
	int end;
	long long moc;
	bool used_edge1;
};

struct End_frag{
	int start;
	long long mult;
	long long limit;
	bool used_edge1;
};
std::set<long long> begin_paths[MAX_N];
std::vector<std::pair<long long, long long>> end_paths[MAX_N];

int n, m;

void calculate_transition(int a) {
	for (int i = 0; i < n; i++) visited[i] = false;
	visited[a] = true;
	std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::less<>> to_process;
	for (auto edge : graph[a]) {
		if (edge.second == 1LL) {
			to_process.push({ 1000000000LL, edge.first });

		}
	}
	while (to_process.size() != 0) {
		auto cur_v = to_process.top();
		to_process.pop();
		if (visited[cur_v.second]) continue;
		visited[cur_v.second] = true;
		long long cur_przep = std::min(cur_v.first, przep[cur_v.second]);
		transitions[a][cur_v.second] = cur_przep;
		std::cout << "";
		for (auto edge : graph[cur_v.second]) {
			if (edge.second == 1LL) {
				to_process.push({ cur_przep,  edge.first });
			}
		}
	}
	
}

int main()
{
	int num_tests = 0;
	std::cin >> num_tests;
	for (int testy = 0; testy < num_tests; testy++)
	{
		std::cin >> n >> m;
		for (int i = 0; i < n; i++) {
			graph[i] = std::vector<std::pair<int, long long>>();
			rev_graph[i] = std::vector<std::pair<int, long long>>();
			for (int j = 0; j < n; j++) {
				transitions[i][j] = -1;
			}
			//transitions[i] = std::vector<std::pair<int, long long>>();
		}
		for (int i = 0; i < n; i++) {
			long long p;
			std::cin >> p;
			przep[i] = p;
		}

		for (int i = 0; i < m; i++) {
			int a, b, w;
			std::cin >> a >> b >> w;
			a--; b--;
			graph[a].push_back({ b,w });
			rev_graph[b].push_back({ a,w });
		}
		for (int i = 0; i < n; i++) {
			std::sort(begin(graph[i]), end(graph[i]), [](auto &a, auto &b) {return a.second < b.second; });
			// SORT EDGES INCREASINGLY
		}

		for (int i = 0; i < n; i++) rev_trans_vec[i] = std::vector<std::pair<int, long long>>();
		for (int a = 0; a < n; a++) {
			calculate_transition(a);
			trans_vec[a] = std::vector<std::pair<int, long long>>();
			for (int b = 0; b < n; b++) {
				if (transitions[a][b] != -1LL) {
					trans_vec[a].push_back({ b, transitions[a][b] });
					rev_trans_vec[b].push_back({ a, transitions[a][b] });
					std::cout << "";
				}
			}
			std::sort(begin(trans_vec[a]), end(trans_vec[a]), [](auto &x, auto &y) {
				return x.second < y.second;
			});
		}

		for (int i = 0; i < n; i++) { //REMOVE EDGES WITH WEIGHT 1
			graph[i].erase(std::remove_if(graph[i].begin(), graph[i].end(), 
							[](std::pair<int, long long> &elem) {return elem.second == 1; }),
				           graph[i].end());
			rev_graph[i].erase(std::remove_if(rev_graph[i].begin(), rev_graph[i].end(),
				[](std::pair<int, long long> &elem) {return elem.second == 1; }),
				rev_graph[i].end());
		}

		std::stack<Start_frag> to_process;
		to_process.push({ 0,1, false });
		long long last_p = przep[n-1];
		for (int i = 0; i < n; i++) {
			begin_paths[i] = std::set<long long>();
			end_paths[i] = std::vector<std::pair<long long, long long>>();
		}

		while (!to_process.empty()) {
			auto x = to_process.top();
			to_process.pop();
			//std::cout << "start " << x.end << " moc " << x.moc << "\n";
			for (auto edge : graph[x.end]) {
				if (x.moc <= std::min(1000000LL, przep[edge.first]) / edge.second) {
					if (begin_paths[edge.first].find(x.moc * edge.second) == end(begin_paths[edge.first])) {

						begin_paths[edge.first].insert(x.moc * edge.second);
						to_process.push({ edge.first, x.moc * edge.second, false });
					}
				}
			}
			if (!x.used_edge1) {
				for (auto edge1 : trans_vec[x.end]) {
					if (x.moc <= edge1.second) {
						if (begin_paths[edge1.first].find(x.moc) == end(begin_paths[edge1.first])) {
							to_process.push({ edge1.first, x.moc, true });
							begin_paths[edge1.first].insert(x.moc);
						}
					}
				}
			}
		}

		long long best_moc = -1;

		std::stack<End_frag> to_process2 = std::stack<End_frag>();
		to_process2.push(End_frag{ n - 1, 1LL, przep[n - 1], false });
		while (!to_process2.empty()) {
			auto x = to_process2.top();
			to_process2.pop();
			//std::cout << "end " << x.start << " mult " << x.mult << " limit " << x.limit << "\n";
			if (x.mult <= 1000) { //PROCESS CONNECTED NODES
				for (auto rev_edge : rev_graph[x.start]) {
					long long new_limit = x.limit / rev_edge.second;
					//std::cout << "  at " << rev_edge.first << "  mult " << rev_edge.second << " new limit " << new_limit << "\n";
					if (0 < new_limit) {
						long long new_mult = x.mult * rev_edge.second;
						if (rev_edge.first == 0) { best_moc = std::max(best_moc, new_mult); }
						new_limit = std::min(przep[rev_edge.first], new_limit);
						to_process2.push({ rev_edge.first, new_mult, new_limit, false });
					}
				}

				if (!x.used_edge1) {
					for (auto edge1 : rev_trans_vec[x.start]) {
						long long new_limit = std::min(x.limit, edge1.second);
						to_process2.push({ edge1.first, x.mult, new_limit, true });
					}
				}
			}
			else {
				end_paths[x.start].push_back({ x.mult, x.limit });
			}

		}

		for (int i = 0; i < n; i++) {
			std::vector<long long> long_paths = std::vector<long long>();
			std::copy(begin_paths[i].begin(), begin_paths[i].end(), std::back_inserter(long_paths));

			std::sort(begin(long_paths), end(long_paths), std::less<>());
			std::sort(begin(end_paths[i]), end(end_paths[i]), std::less<>());
			for (auto x : end_paths[i]) {
				auto res = std::upper_bound(begin(long_paths), end(long_paths), x.second);
				if (res != begin(long_paths)) {
					std::advance(res, -1);
					best_moc = std::max(best_moc, (*res)*x.first);
				}
			}
		}
		/*
		for (int i = 0; i < n; i++) {
			std::cout << "START [" << i << "]  (";
			for (auto x : begin_paths[i]) {
				std::cout << " " << x << " ";
			}
			std::cout << ")\n";
		}

		for (int i = 0; i < n; i++) {
			std::cout << "END [" << i << "]  (";
			for (auto x : end_paths[i]) {
				std::cout << " {" << x.first << ", " << x.second << "} ";
			}
			std::cout << ")\n";
		}*/

		std::cout << best_moc << "\n";
	}

}