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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 201

typedef long long ll;


struct EE {
    int b;
    ll w;
    bool operator==(const EE& other) const {
        return w == other.w && b == other.b;
    }
    bool operator<(const EE& other) const {
        return w == other.w? b < other.b : w > other.w;
    }
};

namespace std {
    template <>
    struct hash<EE> {
        size_t operator()(const EE& s) const {
            return hash<ll>()(s.w*100+s.b);
        }
    };
}
vector<EE> E[MAX];
ll p[MAX], result;
int T,n,m,a;
int vid[MAX];

#define MAP_SIZE 100000037
//#define MAP_SIZE 1000037
#define HASH2 8191
//ll myhash[100][MAP_SIZE];
ll myhash[MAP_SIZE+64];


static bool visited(ll x, int id) {
    ll v = vid[id%MAX];
    ll h = (x*50021+v*1000037)  % 6400002319;
    //% 100000037*64;
    //if(h&15) return false;
    h/=16;
    ll s = myhash[h/64];
    int visited = s & (1<<(h&63));
    myhash[h/64] |= (1<<(h&63));
    return visited;
/*    int h2 = (x%HASH2)+1;
    ll s = myhash[h];
    if(s==0) {
        myhash[h] = (h2<<1) | (v&1) | (1<<((v/2)+14));
        return false;
    } else {
        if ((v&1) == (s&1) && ((s>>1)&0x1fff) == h2) {
            ll visited = (s & (1<<((v/2)+14)));
            myhash[h] |= (1<<((v/2)+14));
            return visited;
        }
    }*/
    return false;
}
void clear_visited() {
//    for(int i=0;i<MAP_SIZE;i++) myhash[i] = 0;
}

#define D(x)

void dfs(int x, int v, int depth=0) {
    int i;
    if(depth > 3100) return;
    for(i=0;i<E[v].size();i++) {
        ll nx = x*E[v][i].w;
        int nv = E[v][i].b;
        D(printf("ns: %d w:%lld p:%lld--\n",ns.b, ns.w, p[ns.b]);)
        if (nx <= p[nv] && (!visited(nx, nv))) {
            D(printf("%d %lld --\n",ns.b, ns.w ));
            if (nv == n) result = max(result, nx);
            dfs(nx,nv, depth+1);
        }
    }
}
int ids[] = {95, 96, 38, 43, 12, 67, 92, 3, 14, 29, 9, 4, 42, 63, 22, 34, 56, 84, 90, 65, 25, 83, 57, 69, 41, 60, 24, 18, 21, 28, 80, 88, 81, 98, 89, 36, 70, 30, 100, 97, 74, 48, 62, 77, 64, 23, 53, 6, 50, 10, 40, 1, 72, 15, 82, 76, 11, 13, 58, 17, 73, 39, 78, 31, 93, 45, 99, 2, 46, 61, 16, 19, 79, 35, 51, 26, 59, 91, 47, 87, 55, 85, 27, 52, 20, 54, 8, 7, 32, 33, 71, 68, 37, 5, 86, 94, 49, 44, 66, 75};
int ids_count=1;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n,&m);
        for(int i=0;i<MAX;i++) E[i].clear();
        for(int i=1;i<=n;i++){
            scanf("%lld", &p[i]);
            vid[i] = ids_count++;
        }
        for(int i=0;i<m;i++) {
            EE e;
            scanf("%d %d %lld", &a, &e.b, &e.w);
            if (a == e.b && e.w == 1) continue;
            E[a].push_back(e);
        }
        for(int i=1;i<=n;i++) {
            std::sort(E[i].begin(), E[i].end());
            auto last = std::unique(E[i].begin(), E[i].end());
            E[i].erase(last, E[i].end());
        }
 

        result = -1;
        if (n == 1) result =1; 
        clear_visited();
        dfs(1, 1);
   
//        fprintf(stderr, "hash size %d col: %d\n", data_size, h_col);
        printf("%lld\n", result);
    }
}