using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define pb push_back
#define size(V) ((int)(V.size()))
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define REP(i, N) for (int i = 0; i < (TT)(N); ++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define oo 66

#define IN "algola.in"
#define OUT "algola.out"
#define N_MAX 1<<6
#define Nd_MAX 5064
#define TT short int

typedef vector<TT> VI;
typedef pair<TT,TT> pi;
typedef vector<string> VS;
template<class T> string toString(T n) {ostringstream ost;ost<<n;ost.flush();return ost.str();}
typedef vector<string> VS;

int Sp[Nd_MAX],Ep[Nd_MAX],Q0,Scp,rez,N,M,S,D,Tmax;
TT Q[1<<17],Ta[Nd_MAX],SD[N_MAX];
char C[1<<17];
vector< vector<pi> > B(N_MAX);
vector<VI> A(Nd_MAX);
bool viz[Nd_MAX];

II void scan()
{
    freopen(IN,"r",stdin);
    freopen(OUT,"w",stdout);
    scanf("%d%d",&N,&M);

    FOR(i,1,N)
    {
        scanf("%d",&SD[i]);
        Scp += SD[i];
    }

    int x,y,c;
    FOR(i,1,M)
    {
        scanf("%d%d%d",&x,&y,&c);
        B[x].pb( mp(y,c) );
        B[y].pb( mp(x,c) );
    }
    Tmax = Scp + N;
}

II char querry(int x,int y)
{
	FOR(j,Sp[x],Ep[x])
		if(Q[j] == y)
			return C[j];
	return 0;
}

II void update(int x,int y,int val)
{
	FOR(j,Sp[x],Ep[x])
		if(Q[j] == y)
		{
			C[j] += val;
			return;
		}
	return;
}

II void build(int x,int y,int val)
{
	FOR(j,Sp[x],Ep[x])
		if(Q[j] == y)
		{
			C[j] = val;
			return;
		}
	return;
}

II void BF(int T)
{
	CC(viz);
	CC(Ta);
	viz[S] = true;
	int Que[Nd_MAX];
	Que[Que[0]=1] = S;
	
    FOR(i,1,Que[0])
	{
	    int nod = Que[i];
		if(nod == D)
			return;
		
		FOR(j,Sp[nod],Ep[nod])
		{
			int fiu = Q[j];
			if(!viz[fiu] && querry(nod,fiu) )
			{
			    Ta[fiu] = nod;
				viz[fiu] = true;
				Que[++Que[0]] = fiu;
			}
		}
	}
}

II bool flux(int T)
{
	if(!viz[D])
		return false;
	FOR(i,N * (T-1) + 1,N * T)
	{
		int Snod = i;
		if(!querry(Snod,D) || !Ta[Snod] || !viz[Snod])
			continue;

		char aux(oo);
		for(int nod = Snod;Ta[nod];aux = min(aux,querry(Ta[nod],nod) ),nod = Ta[nod]);
		if(!aux)
			continue;
		update(Snod,D,-aux);
		update(D,Snod,+aux);
		for(int nod = Snod;Ta[nod];update(Ta[nod],nod,-aux),update(nod,Ta[nod],+aux),nod = Ta[nod]);
		rez += aux;
	}
	return true;
}

II bool flow(int T)
{
	int aux = Q0;
	Q0 = Ep[T * N + N];
	D = N * T + 1;
	
	FOR(i,1,N)
		build(S,i,SD[i]),
		build(i,S,0);
		
	FOR(ti,0,Tmax-1)
    FOR(i,1,N)
    {
        FORit(it,B[i])
            build(i + ti * N,it->f + (ti+1) * N,it->s),
			build(it->f + (ti+1) * N,i + ti * N,0);

		build(i + ti * N,i + (ti+1) * N,oo);
		build(i + (ti+1) * N,i + ti * N,0);
    }
	
	rez = 0;
	for(BF(T);flux(T);BF(T));
	Q0 = aux;
	
	return rez == Scp;
}

II void solve()
{
    S = N * Tmax + N + 1;
	
    FOR(i,1,N)
        A[S].pb(i),
		A[i].pb(S);

    FOR(ti,0,Tmax-1)
    FOR(i,1,N)
    {
        FORit(it,B[i])
            A[i + ti * N].pb(it->f + (ti+1) * N),
			A[it->f + (ti+1) * N].pb(i + ti * N); 

        A[i + ti * N].pb(i + (ti+1) * N);
		A[i + (ti+1) * N].pb(i + ti * N);
    }
	Sp[S] = Q0+1;
	FORit(it,A[S])
		Q[++Q0] = *it;
	Ep[S] = Q0;
	
	FOR(i,1,Tmax * N)
	{
		Sp[i] = Q0+1;
		FORit(it,A[i])
			Q[++Q0] = *it;
		Ep[i] = Q0;
	}
	vector<VI> ().swap(A);

	int m,step;
	for(step = 1;step <= Tmax;step <<= 1);
    for(m=0;step;step >>= 1)
        if(m+step <= Tmax && flow(m+step-1) == false)
			m += step;
	
	printf("%d\n",m);
//	printf("Time %d\n",clock());
}

int main()
{
    scan();
    solve();
    return 0;
}