#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn=5e4+10;
const int mm=2e5+10;
const ll INF=LLONG_MAX;
struct Edge{
    int to,t;
};
struct Node{
    int id;
    ll te;
    bool operator<(const Node& other)const {
        return te>other.te;
    }
};
vector<Edge> j[mn];
ll d[mn];
int a[mn];
ll gnt(ll ct,int i) 
{
    if(ct%i==0) return ct;
    return ct+i-(ct%i);
}
ll D(int n,int st,int e) 
{
    fill(d,d+n+1,INF);
    priority_queue<Node> pq;
    d[st]=gnt(0,a[st]);
    pq.push({st,d[st]});
    while(!pq.empty()) 
	{
        Node ne=pq.top();
        pq.pop();
        int u=ne.id;
        ll ct=ne.te;
        if(u==e) return ct;
        if(ct>d[u]) continue;
        for(const Edge& ee:j[u]) 
		{
            int v=ee.to,tt = ee.t;
            if (ct >= tt) continue;
            ll nt=gnt(ct+1,a[v]);
            if(nt<d[v]) 
			{
                d[v]=nt;
                pq.push({v,nt});
            }
        }
    }
    return -1;
}

int main() 
{
    freopen("open.in","r",stdin);
	freopen("open.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=0;i<m;++i) 
	{
        int u,v,t;
        cin>>u>>v>>t;
        j[u].push_back({v,t});
        j[v].push_back({u,t});
    }
    ll ans=D(n,1,n);
    cout<<ans<<endl;
    return 0;
}