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[Nd_MAX];
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 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] && C[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(!C[Snod][D] || !Ta[Snod] || !viz[Snod])
			continue;

		char aux(oo);
		for(int nod = Snod;Ta[nod];aux = min(aux,C[Ta[nod]][nod]),nod = Ta[nod]);
		if(!aux)
			continue;
		C[Snod][D] -= aux;
		C[D][Snod] += aux;
		for(int nod = Snod;Ta[nod];C[Ta[nod]][nod] -= aux,C[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)
		C[S][i] = SD[i],C[i][S] = 0;
		
	FOR(ti,0,Tmax-1)
    FOR(i,1,N)
    {
        FORit(it,B[i])
            C[i + ti * N][it->f + (ti+1) * N] = it->s,
			C[it->f + (ti+1) * N][i + ti * N] = 0;

		C[i + ti * N][i + (ti+1) * N] = oo;
		C[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,0,S)
		C[i] = (char *) malloc((S+4) * sizeof(char) );
	
    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;
}