#include <stdio.h>
#include <string.h>
#include <vector>
#define NMAX 55
#define LMAX 101
#define HMAX 5601
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
int n,m,s,B[NMAX],sursa,dest,C[HMAX][HMAX],F[HMAX][HMAX];
vector <int> A[HMAX];
int flow,fmin,dad[HMAX],Q[HMAX];
char viz[HMAX];
void read()
{
    scanf("%d%d",&n,&m);
    int i,j,x,y,z,x1,y1;
    for (i=1; i<=n; i++)
        scanf("%d",&B[i]),s+=B[i];
    s-=B[1];
    sursa=1;
    for (i=1; i<=n; i++)
    {
        A[1].pb(i+1); A[i+1].pb(1);
        C[1][i+1]=B[i];
    }
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        for (j=1; j<LMAX; j++)
        {
            x1=x+1+(j-1)*n; y1=y+1+j*n;
            A[x1].pb(y1); A[y1].pb(x1);
            C[x1][y1]=z; 
            x1=x+1+j*n; y1=y+1+(j-1)*n;
            A[x1].pb(y1); A[y1].pb(x1);
            C[y1][x1]=z; 
        }
    }
    for (j=1; j<LMAX; j++)
    {
        for (i=2; i<=n; i++)
        {
            x=1+i+(j-1)*n; y=1+i+j*n;
            A[x].pb(y); A[y].pb(x);
            C[x][y]=HMAX;
        }
    }
}
inline int min(int x,int y)
{
    return x<y ? x : y;
}
int BF()
{
    Q[0]=1; Q[1]=1;
    memset(viz,0,sizeof(viz));
    viz[1]=1;
    int i,j,nod,vec;
    for (i=1; i<=Q[0]; i++)
    {
        nod=Q[i];
        for (j=0; j<A[nod].size(); j++)
        {
            vec=A[nod][j];
            if (C[nod][vec]==F[nod][vec] || viz[vec] || vec>dest)
                continue ;
            viz[vec]=1;
            Q[++Q[0]]=vec;
            dad[vec]=nod;
            if (vec==dest)
                return 1;
        }
    }
    return 0;
}
void flux()
{
    int i,nod;
    while (BF())
    {
        for (i=0; i<A[dest].size(); i++)
        {
            nod=A[dest][i];
            if (F[nod][dest]==C[nod][dest] || !viz[nod]) 
                continue;
            dad[dest]=nod;
            fmin=INF;
            for (nod=dest; nod!=1; nod=dad[nod])
                fmin=min(fmin,C[dad[nod]][nod]-F[dad[nod]][nod]);
            for (nod=dest; nod!=1; nod=dad[nod])
            {
                F[dad[nod]][nod]+=fmin;
                F[nod][dad[nod]]-=fmin;
            }
            flow+=fmin;
        }
    }
}
void solve()
{
    int i;
    for (i=1; i<LMAX; i++)
    {
        dest=2+i*n;
        flux();
        if (flow==s)
        {
            printf("%d\n",i);
            return ;
        }
    }
}
int main()
{
    freopen("algola.in","r",stdin);
    freopen("algola.out","w",stdout);
    read();
    solve();
    return 0;
}