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
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<ll,int>
#define piii pr<ll,pii>
using namespace std;
vector<pii> e[102];
vector<pii> g[102];
bool vd[102][100005];
int ls[102][100005];
ll mx[102][10004];
ll a[102];
void sl()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) e[i].clear(),g[i].clear();
	int u,v;
	ll w;
	while(m--)
	{
		cin>>u>>v>>w;
		u--;
		v--;
		e[u].push_back(mp(w,v));
		g[v].push_back(mp(w,u));
	}
	for(int i=0;i<n;i++) for(int j=0;j<=100000;j++) vd[i][j]=0;
	queue<pii> q;
	q.push(mp(1,0));
	while(q.size())
	{
		pii f=q.front();
		q.pop();
		if(vd[f.s][f.f]) continue;
		vd[f.s][f.f]=1;
		for(pii t:e[f.s]) if(t.f*f.f<=min(100000ll,a[t.s])) q.push(mp(t.f*f.f,t.s));
	}
	for(int i=0;i<n;i++) for(int j=1;j<=100000;j++) ls[i][j]=vd[i][j]?j:ls[i][j-1];
	for(int i=0;i<n;i++) for(int j=0;j<=10000;j++) mx[i][j]=0;
	priority_queue<piii> qq;
	qq.push(mp(a[n-1],mp(1,n-1)));
	while(qq.size())
	{
		piii f=qq.top();
		qq.pop();
		f.f=min(f.f,a[f.s.s]);
		if(mx[f.s.s][f.s.f]>=f.f) continue;
		mx[f.s.s][f.s.f]=f.f;
		for(pii t:g[f.s.s]) if(t.f*f.s.f<=10000) qq.push(mp(f.f/t.f,mp(t.f*f.s.f,t.s)));
	}
	ll ans=0;
	for(int i=0;i<n;i++) for(int j=1;j<=10000;j++)
	{
		for(pii t:g[i])
		{
			ans=max(ans,ls[t.s][min(100000ll,mx[i][j]/t.f)]*t.f*j);
		}
	}
	if(ans>0) cout<<ans<<endl;
	else cout<<"-1\n";
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("op.txt","w",stdout);
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) sl();
	return 0;
}