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

using namespace std;

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

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

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

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

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

        if (j==T) continue;

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

    return V[D][T];
}

bool Check (int T)
{
    memset(Flow, 0, sizeof(Flow));

    int MaxFlow=0;
    while (BF(T))
    {
        int FMIN=INF;
        int i, j;

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

        for (i=D, j=T; i!=S; i=Father[i][j], j--)
        {
            Flow[Father[i][j]][j-1][i][j]+=FMIN;
            Flow[i][j][Father[i][j]][j-1]-=FMIN;
        }

        MaxFlow+=FMIN;
    }

    return MaxFlow>=TSum;
}


int Search ()
{
    int P=2, U=102, M, ANS=U;

    while (P<=U)
    {
        M=(P+U)/2;

        if (Check(M))
        {
            ANS=M;
            U=M-1;
        }
        else
            P=M+1;
    }

    return ANS-2;
}

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];

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


    G[D].push_back(1);
    G[1].push_back(D);
    Cap[1][D]=INF;

    for (int i=1; i<=M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;

        Cap[a][b]=c;
        Cap[b][a]=c;

        G[a].push_back(b);
        G[b].push_back(a);
    }

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

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

    return 0;
}