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 < (int)(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 1<<30

#define IN "algola.in"
#define OUT "algola.out"
#define N_MAX 1<<6
#define Nd_MAX 5024

typedef vector<int> VI;
typedef pair<int,int> 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 Scp,rez,N,M,S,D,Tmax;
int Ta[Nd_MAX],C[Nd_MAX][Nd_MAX],CI[Nd_MAX][Nd_MAX],SD[N_MAX];
vector< vector<pi> > B(N_MAX);
vector<VI> A;
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;
}

void BF()
{
	CC(viz);
	CC(Ta);
	viz[S] = true;
	VI Q;
	Q.pb(S);

    for(int i = 0;i < size(Q);++i)
	{
	    int nod = Q[i];
		int l = size(A[nod]) - 1;

		FOR(j,0,l)
		{
			int fiu = A[nod][j];
			if(!viz[fiu] && C[nod][fiu])
			{
			    Ta[fiu] = nod;
				viz[fiu] = true;
				Q.pb(fiu);
			}
		}
	}
}

bool flux(int T)
{
	int flux(0);
	if(!Ta[D])
		return false;

	FOR(i,1 + T * N,N + T * N)
	{
		if(!C[i][D] || !viz[i])
			continue;
		int aux(C[i][D]);
	//	printf("pentru %d %d %d\n",i,Ta[i],Ta[ Ta[i] ]);
		
		for(int nod = i;Ta[nod];aux = min(aux,C[Ta[nod]][nod]),nod = Ta[nod]);
		if(!aux)
			continue;
		C[i][D] -= aux;
		C[D][i] += aux;
		for(int nod = i;Ta[nod];C[Ta[nod]][nod] -= aux,C[nod][Ta[nod]] += aux,nod = Ta[nod]);

		flux += aux;
	}
	rez += flux;
	return true;
}

II bool flow(int T)
{
    //regulam destinatia grafului
    CP(C,CI);
    C[T * N + 1][D] = oo;

    rez = 0;
    for(BF();flux(T);BF());
	return rez == Scp;
}

II void solve()
{
    //regulam initial graful
    S = N * Tmax + N + 1;
    D = N * Tmax + N + 2;

    A.resize(N * Tmax + N + 4);
    FOR(i,1,N)
        A[S].pb(i),
		A[i].pb(S),
        CI[S][i] = SD[i];

    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), 
            CI[i + ti * N][it->f + (ti+1) * N] = it->s;

        A[i + ti * N].pb(i + (ti+1) * N);
		A[i + (ti+1) * N].pb(i + ti * N);
        CI[i + ti * N][i + (ti+1) * N] = oo;
        A[i + ti * N].pb(D);
		A[D].pb(i + ti * N);
    }

    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);
}

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