/**
imi construiesc o retea de tipul cu noduri (nod, timp)
in reteaua asta voi avea muchii
(nod, timp) -> (nod, timp+1) cu capacitate infint
(a, timp) -> (b, timp+1) cu capacitate c daca intre a si b exista o muchie de limita c in graful initial
(source, 0) -> (nod, 1) cu capacitate A[nod] (valoarea data initial)

in reteaua asta fiecare unitate de flux imi reprezinta o persoana

acum pot sa fac o cautare binara ca sa gasesc timpul minim
sau pot sa adaug treptat noduri in retea si sa maresc fluxul pana cand fluxul este maxim
*/

#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NM 5010

using namespace std;

ifstream f("algola.in");
ofstream g("algola.out");

typedef pair<int, int> PI;
const int INF=999999;
int N, M, TSum, MaxFlow;
vector<PI> E[NM];
vector<int> G[NM];
int Cap[NM][NM], Flow[NM][NM], Father[NM];
int A[NM];
int S, D;
bool V[NM];
queue<int> Q;

bool BF ()
{
    memset(V, 0, sizeof(V));
    V[S]=1;
    Q.push(S);

    int i;
    vector<int>::iterator it;

    while (!Q.empty())
    {
        i=Q.front();
        Q.pop();

        if (i==D) continue;

        for (it=G[i].begin(); it!=G[i].end(); ++it)
            if (V[*it]==0 && Flow[i][*it]<Cap[i][*it])
            {
                V[*it]=1;
                Q.push(*it);
                Father[*it]=i;
            }
    }

    return V[D];
}

void DoMaxFlow ()
{
    while (BF())
        for (vector<int>::iterator it=G[D].begin(); it!=G[D].end(); ++it)
            if (V[*it] && Flow[*it][D]<Cap[*it][D])
            {
                Father[D]=*it;
                int FMIN=INF;

                for (int i=D; i!=S; i=Father[i])
                    FMIN=min(FMIN, Cap[Father[i]][i] - Flow[Father[i]][i]);

                for (int i=D; i!=S; i=Father[i])
                {
                    Flow[Father[i]][i]+=FMIN;
                    Flow[i][Father[i]]-=FMIN;
                }

                MaxFlow+=FMIN;
            }
}

void Build (int T)
{
    for (int i=1; i<=N; i++)
    {
        int a, b;

        a=N*(T-1)+i;
        G[a].push_back(a+N);
        G[a+N].push_back(a);
        Cap[a][a+N]=INF;

        for (vector<PI>::iterator it=E[i].begin(); it!=E[i].end(); ++it)
        {
            b=N*T+it->first;

            G[a].push_back(b);
            G[b].push_back(a);
            Cap[a][b]=it->second;
        }
    }
}

int Solve ()
{
    int T;

    for (T=1; MaxFlow<TSum; T++)
    {
        Build(T);
        D=T*N+1;
        DoMaxFlow();
    }

    return T-1;
}

int main ()
{
    f >> N >> M;
    S=0;
    D=N+1;

    for (int i=1; i<=N; i++)
    {
        f >> A[i];
        TSum+=A[i];

        G[S].push_back(i);
        G[i].push_back(S);
        Cap[S][i]=A[i];
    }

    for (int i=1; i<=M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        E[a].push_back(make_pair(b, c));
        E[b].push_back(make_pair(a, c));
    }

    g << Solve() << '\n';

    f.close();
    g.close();

    return 0;
}