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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n,m;
	cin>>n>>m;
	vector<long long int>p(n+1);
	for(int i=0 ;i<n; i++)
		cin>>p[i+1];
	vector<vector<pair<int,long long int>>>g(n+1),g1(n+1);
	for(int i=0 ;i<m; i++)
	{
		long long int a,b,c;
		cin>>a>>b>>c;
		g[a].push_back({b,c});
		g1[b].push_back({a,c});
	}
	vector<unordered_map<long long int,bool>>mp(n+1);
	vector<queue<long long int>>q(n+1);
	q[1].push(1);
	mp[1][1]=1;
	long long int res=-1;
	priority_queue<pair<long long int,int>>pq;
	vector<long long int>cap(n+1,0);
	cap[n]=p[n];
	pq.push({cap[n],n});
	while(!pq.empty())
	{
		auto k=pq.top();
		int w=k.second;
		pq.pop();
		for(auto i:g1[w])
			if(cap[i.first]<cap[w]/i.second)
			{
				cap[i.first]=cap[w]/i.second;
				pq.push({cap[i.first],i.first});
			}
	}
	for(int i=1; i<=n; i++)
		p[i]=min(p[i],cap[i]);
	//cout<<"murzyn\n";
	function<void(int)>dfs=[&](int w)
	{
		while(!q[w].empty())
		{
			long long int k=q[w].front();
			//cout<<w<<" "<<k<<"\n";
			if(w==n)
				res=max(res,k);
			q[w].pop();
			for(auto i:g[w])
			{
				if(k*i.second<=p[i.first]&&mp[i.first][k*i.second]==0)
				{
					q[i.first].push(k*i.second);
					mp[i.first][k*i.second]=1;
				}
			}
		}
		for(auto i:g[w])
			if(!q[i.first].empty())
				dfs(i.first);
	};
	dfs(1);
	cout<<res<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--)
		solve();
}