#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
using namespace std;

#define DEBUG_LEVEL 0

#define CALC_TIME
//correct: 845166960 = 2^4 * 3^4 * 5 * 11 * 71 * 167
//my:      819954688 = 2^10 * 7 * 73 * 1567
// 

#if DEBUG_LEVEL > 0
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#if DEBUG_LEVEL > 1
    #define DEBUG2(x) x
#else
    #define DEBUG2(x)
#endif
#if DEBUG_LEVEL > 2
    #define DEBUG3(x) x
#else
    #define DEBUG3(x)
#endif

#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) auto x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())

const int MAX_ROUTERS = 101;
const int MAX_AMPLIFIERS = 201;
const int MAX_LIMIT = 1000000000;

struct Amplifier {
    int from;
    int to;
    long long factor;
    bool operator<(const Amplifier& other) const {
        return from!=other.from ? from<other.from
            : to!=other.to ? to<other.to
            : factor<other.factor;
    }
};
struct Router {
    long long limit;
    set<Amplifier> paths;
    bool visited;
    long long absoluteValue;
//    set<int> powerOptions;
    map<int,long long> cyclesFound; // length -> max power at this point
} routers[MAX_ROUTERS];
int routersNo, amplifiersNo;

set<long long> endRouterPowerOptions;

ostream& operator<<(ostream& os, const Amplifier& a) {
    return os << "{" << a.from << "->" << a.to << ", p=" << a.factor << "}";
}
template<typename _T, typename _U> ostream& operator<<(ostream& os, const pair<_T, _U>& p) {
    return os << p.first << ": " << p.second;
}
const unsigned int MAX_SIZE_TO_PRINT = 1000;
template<typename _T> ostream& operator<<(ostream& os, const vector<_T>& v) {
    os << "[";
    if (v.size() > MAX_SIZE_TO_PRINT) {
        os << "vector with " << v.size() << " items";
    } else {
        FOREACH(it, v) {
            cerr<<(it==v.begin()?"":",")<<*it;
        }
    }
    return os << "]";
}
template<typename _T> ostream& operator<<(ostream& os, const vector<_T*>& v) {
    os << "[";
    if (v.size() > MAX_SIZE_TO_PRINT) {
        os << "vector with " << v.size() << " items";
    } else {
        FOREACH(it, v) {
            cerr<<(it==v.begin()?"":", ");
            if (*it == nullptr) {
                cerr << "null";
            } else {
                cerr << **it;
            }
        }
    }
    return os << "]";
}
template<typename _T> ostream& operator<<(ostream& os, const set<_T>& s) {
    os << "[";
    if (s.size() > MAX_SIZE_TO_PRINT) {
        os << "set with " << s.size() << " items";
    } else {
        FOREACH(it, s) {
            cerr<<(it==s.begin()?"":", ")<<*it;
        }
    }
    return os << "]";
}
template<typename _K, typename _V> ostream& operator<<(ostream& os, const map<_K,_V>& m) {
    os << "[";
    if (m.size() > MAX_SIZE_TO_PRINT) {
        os << "map with " << m.size() << " items";
    } else  {
        FOREACH(it, m) {
            cerr<<(it==m.begin()?"":", ")<<it->first<<":"<<it->second;
        }
    }
    return os << "]";
}
void printGraph() {
    REP(x,routersNo) {
        Router& r = routers[x+1];
        cerr << x+1 << ": limit="<<r.limit
            <<", visited="<<(r.visited?"true":"false")
            <<", absoluteValue="<<r.absoluteValue
            <<", paths: "<<r.paths
//            <<", powerOptions: "<<r.powerOptions
            <<", cyclesFound: "<<r.cyclesFound
            <<endl;
    }
}

void setCycle(Router& router, long long factor, long long limit) {
    auto find = router.cyclesFound.find(factor);
    if (find == router.cyclesFound.end()) {
        DEBUG2(cerr<<"setCycle(router #"<<(&router-routers)<<", "<<factor<<", "<<limit<<") -> set new to "<<limit<<endl;)
        router.cyclesFound[factor] = limit;
    } else {
        DEBUG2(cerr<<"setCycle(router #"<<(&router-routers)<<", "<<factor<<", "<<limit<<") -> update existing to max("<<find->second<<","<<limit<<") = "<<limit<<endl;)
        find->second = max(find->second, limit);
    }
}

map<int,long long> mergeCycles(const map<int,long long>& a, const map<int,long long>& b, int factorB, long long limit) {
    map<int, long long> result;
    auto iterA = a.begin();
    auto iterB = b.begin();
    while (iterA != a.end() && iterB != b.end()) {
        if (iterA->first < iterB->first)
            result.insert(*(iterA++));
        else if(iterB->first < iterA->first) {
            result.insert({iterB->first, min(iterB->second * factorB, limit)});
            ++iterB;
        } else {
            result.insert({iterA->first, min(limit, max(iterA->second, iterB->second * factorB))});
            ++iterA, ++iterB;
        }
    }
    while(iterA != a.end()) {
        result.insert(*(iterA++));
    }
    while(iterB != b.end()) {
        result.insert({iterB->first, min(iterB->second * factorB, limit)});
        ++iterB;
    }
    DEBUG(cerr<<"merge cycles("<<a<<", "<<b<<", "<<factorB<<", "<<limit<<") -> "<<result<<endl;)
    return result;
}

void findCycles(int source, vector<const Amplifier*>& path, long long limit) {
    Router& currentRouter = routers[source];
    currentRouter.visited = true;
    unsigned int knownCycles = 2000000000; // some large number
    while (currentRouter.cyclesFound.size() != knownCycles) {
        DEBUG(cerr<<"findCycles "<<source<<", path is: "<<path<<", limit is "<<limit<<"; knownCycles="<<knownCycles<<"/"<<currentRouter.cyclesFound.size()<<endl);
        knownCycles = currentRouter.cyclesFound.size();
        FOREACH(it, currentRouter.paths) {
            DEBUG2(cerr<<"processing path "<<*it;)
            Router& target = routers[it->to];
            if (target.visited) {
                DEBUG2(cerr<<" visited - got cycle!";)
                if (target.limit >= currentRouter.absoluteValue * it->factor) {
                    long long cycleFactor = currentRouter.absoluteValue/target.absoluteValue * it->factor;
                    if (cycleFactor != 1 && cycleFactor < MAX_LIMIT) {
                        long long pathLimit = limit;
                        DEBUG2(cerr<<" with a factor of "<<cycleFactor<<" - checking path "<<endl;)
                        for (auto pathIter = path.rbegin(); pathIter != path.rend() && (*pathIter)->from != it->to; ++pathIter) {
                            // DEBUG2(cerr<<"  check path "<<*pathIter<<endl;)
                            setCycle(routers[(*pathIter)->from], cycleFactor, pathLimit);
                            pathLimit /= (*pathIter)->factor;
                        }
                        setCycle(target, cycleFactor, min(limit*it->factor, target.limit));
                    } else {
                        DEBUG2(cerr<<" with a factor of 1..." << endl;)
                    }
                } else {
                    DEBUG2(cerr<<" but it's unreachable..."<<endl;)
                }
            } else {
                DEBUG2(cerr<<" not visited";)
                long long minPowerAtTarget = currentRouter.absoluteValue * it->factor;
                bool reachable = (minPowerAtTarget <= target.limit);
                DEBUG2(cerr<<", reachable="<<reachable<<endl;)
                if (reachable) {
                    target.absoluteValue = currentRouter.absoluteValue * it->factor;
                    path.push_back(&*it);
                    findCycles(it->to, path, min(limit*it->factor, target.limit));
                    path.pop_back();
                }
            }
        }
    }
    currentRouter.visited = false;
}

long long findHighestPossiblePower(
        long long entryPower,
        long long limit,
        const vector<pair<long long,int>>& applicableCycles,
        const vector<pair<long long,int>>::const_iterator& pos,
        int depth,
        const map<int,int>& distanceToNextLowerValue) {
    // pair.first - limit; pair.second - factor
    DEBUG3(cerr<<string(2*depth, ' ')<<">findHighestPossiblePower("<<entryPower<<", "<<limit<<", "<<*pos<<")"<<endl;)
    long long currentFactor = pos->second;
    long long powerWithHighestCurrentFactor = entryPower;
    long long limitForCurrentFactor = min(limit, pos->first);
    int maxPowerFactor=1;
    while(powerWithHighestCurrentFactor * currentFactor <= limitForCurrentFactor) {
        powerWithHighestCurrentFactor *= currentFactor;
        ++maxPowerFactor;
    }

    long long maxResult = powerWithHighestCurrentFactor;
    while (powerWithHighestCurrentFactor >= entryPower) {
        DEBUG3(cerr<<string(2*depth, ' ')<<">while loop with current power "<<powerWithHighestCurrentFactor<<"/"<<entryPower<<endl;)
        for (auto cycle = next(pos); cycle != applicableCycles.end(); ++cycle) {
            DEBUG3(cerr<<string(2*depth, ' ')<<">loop with cycle="<<*cycle<<", index="<<distance(applicableCycles.begin(), cycle)<<endl;)
            long long maybeNextPower = powerWithHighestCurrentFactor * cycle->second;
            if (maybeNextPower <= limit) {
                if (maybeNextPower <= cycle->first) {
                    DEBUG2(cerr<<string(2*depth, ' ')<<"for cycle "<<*cycle<<" maybeNextPower="<<maybeNextPower<<" matches limits "<<limit<<" and "<<cycle->first<<" - entering deeper..."<<endl;)
                    maxResult = max(maxResult, findHighestPossiblePower(maybeNextPower, limit, applicableCycles, cycle, depth+1, distanceToNextLowerValue));
                } else {
                    DEBUG2(cerr<<string(2*depth, ' ')<<"for cycle "<<*cycle<<" maybeNextPower="<<maybeNextPower<<" matches limit "<<limit<<" but failed at cycle limit " << cycle->first <<endl;)
                }
            } else {
                int distanceToNextLower = distanceToNextLowerValue.at(cycle->second);
                DEBUG2(cerr<<string(2*depth, ' ')<<"for cycle "<<*cycle<<" maybeNextPower="<<maybeNextPower<<" exceeded limit "<<limit<<" - distance to lower value is "<<distanceToNextLower<<endl;)
                if (distanceToNextLower == -1)
                    break;
                else
                    advance(cycle, distanceToNextLower-1); // it will be incremented in loop anyway
            }
        }
        powerWithHighestCurrentFactor /= currentFactor;
    }
    DEBUG(cerr<<string(2*depth, ' ')<<"highest possible power for "<<(entryPower%currentFactor == 0 ? entryPower/currentFactor : entryPower)<<", entry pos "<< distance(applicableCycles.begin(), pos) <<" and factor "<<currentFactor<<" is "<<maxResult<<"; maxPowerFactor="<<maxPowerFactor<<", limit="<<limit<<endl;)
    return maxResult;
}

long long findHighestPossiblePower(const Router& router, const map<int,long long>& applicableCycles, set<int>& powerOptions) {
    vector<pair<long long,int>> reversedMap;
    reversedMap.reserve(applicableCycles.size());
    FOREACH(it, applicableCycles)
        reversedMap.push_back({it->second, it->first});
    sort(reversedMap.begin(), reversedMap.end(), [](const auto& a, const auto& b){return a.first==b.first ? a.second < b.second : a.first < b.first;});
    vector<pair<int,int>> positions; // pair<value, position>
    map<int,int> distanceToNextLowerValue;
    int pos = reversedMap.size();
    for(auto iter = reversedMap.rbegin(); iter != reversedMap.rend(); ++iter) {
        --pos;
        //pair { iterator, wasInserted}
        while(!positions.empty() && positions.back().first > iter->second)
            positions.pop_back();
        if (positions.empty()) {
            distanceToNextLowerValue[iter->second] = -1;
        } else {
            distanceToNextLowerValue[iter->second] = positions.back().second - pos;
        }
        positions.push_back({iter->second, pos});
        DEBUG3(cerr << " processed "<<*iter<<", result is ["<<iter->second<<"] = "<<distanceToNextLowerValue[iter->second]<<endl;)
        DEBUG3(cerr<<"positions: "<<positions<<endl;)
    }
    DEBUG(cerr<<"reversed map is "<<reversedMap<<endl;)
    DEBUG(cerr<<"distanceToNextLowerValue is "<<distanceToNextLowerValue<<endl;)
    long long maxResult = -1;
    FOREACH(powerOption, powerOptions) {
        FOREACH(startIter, reversedMap) {
            maxResult = max(maxResult, findHighestPossiblePower(*powerOption, router.limit, reversedMap, startIter, 0, distanceToNextLowerValue));
        }
    }
    DEBUG(cerr<<"highest possible power is "<<maxResult<<endl;)
    return maxResult;
}

void processEndRouter(long long limit, const map<int,long long>& applicableCycles, set<int>& powerOptions) {
    Router& endRouter = routers[routersNo];
    DEBUG(cerr<<"processEndRouter - limit="<<limit<<", cycles="<<applicableCycles<<",powerOptions="<<powerOptions<<endl;)
    endRouterPowerOptions.insert(findHighestPossiblePower(endRouter, applicableCycles, powerOptions));
}

void findRoute(int source, long long limit, map<int,long long> applicableCyclesForParent, int pathFactor, set<int>& powerOptions) {
    Router& currentRouter = routers[source];
    DEBUG(cerr<<"findRoute "<<source<<", limit is "<<limit<<"; applicableCyclesForParent="<<applicableCyclesForParent<<", pathFactor="<<pathFactor<<",powerOptions="<<powerOptions<<endl;)
    currentRouter.visited = true;
    map<int,long long> applicableCyclesForCurrent = mergeCycles(currentRouter.cyclesFound, applicableCyclesForParent, pathFactor, currentRouter.limit);
    if (source == routersNo) {
        processEndRouter(limit, applicableCyclesForCurrent, powerOptions);
        currentRouter.visited = false;
        return;
    }
    FOREACH(edge, currentRouter.paths) {
        Router& targetRouter = routers[edge->to];
        if (!targetRouter.visited) {
            bool reachable = false;
            set<int> targetPowerOptions;
            FOREACH(powerOption, powerOptions) {
                if (*powerOption * edge->factor <= targetRouter.limit) {
                    targetPowerOptions.insert(*powerOption * edge->factor);
                    reachable = true;
                }
            }
            DEBUG(cerr<<"processing path "<<*edge<<" - not visited, reachable="<<reachable<<endl;)
            if (reachable) {
                findRoute(edge->to, min(limit*edge->factor, targetRouter.limit), applicableCyclesForCurrent, edge->factor, targetPowerOptions);
            }
        } else {
            DEBUG(cerr<<"processing path "<<*edge<<" - already visited"<<endl;)
        }
    }
    currentRouter.visited = false;
}

int solveCase() {
    endRouterPowerOptions.clear();
    cin>>routersNo>>amplifiersNo;
    REP(x,routersNo) {
        Router& router = routers[x+1];
        cin>>router.limit;
        router.paths.clear();
        router.visited = false;
        router.absoluteValue = 0;
//        router.powerOptions.clear();
        router.cyclesFound.clear();
    }
    int source,target,factor;
    REP(x,amplifiersNo) {
        cin>>source>>target>>factor;
        routers[source].paths.insert({source,target,factor});
    }
    DEBUG(
        cerr << "graph after loading: "<<endl;
        printGraph();
    );
    routers[1].absoluteValue = 1;

    vector<const Amplifier*> path;
    findCycles(1, path, routers[1].limit);
    DEBUG(
        cerr << "graph after cycles: "<<endl;
        printGraph();
    );
    
    set<int> powerOptions = {1};
    findRoute(1, routers[1].limit, {}, 1, powerOptions);
    DEBUG(
        cerr << "graph after algorithm: "<<endl;
        printGraph();
    );

    return endRouterPowerOptions.empty() ? -1 : *endRouterPowerOptions.rbegin();
}

void solve() {
    int t;
    cin >> t;
    REP(x,t) {
        cout << solveCase() << endl;
    }
}

#ifdef CALC_TIME
#include <ctime>
#endif

int main() {
    ios_base::sync_with_stdio(0);
#ifdef CALC_TIME
    clock_t begin = clock();
#endif

    solve();
#ifdef CALC_TIME
    cerr << "TIME: " << float(clock()-begin)/CLOCKS_PER_SEC << " s " << endl;
#endif
}