#include<stdio.h>
#define Nm 51
#define Mm 300
#define Tm 100
#define Nodem ((Tm+1)*Nm+1)
#define min(a,b) ((a)<(b)?(a):(b))
char Poz[Nodem][Nodem];
int G[Nodem][Nm],D[Nodem],X[Mm],Y[Mm],L[Mm],A[Nm],n,m,a;
int F[Nodem][Nm],C[Nodem][Nm],Q[Nodem],Pre[Nodem],Min[Nodem],node,source,sink;

void read()
{
    int i;

    freopen("algola.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
    {
        scanf("%d",A+i);
        a+=A[i];
    }
    for(i=0;i<m;++i)
    {
        scanf("%d%d%d",X+i,Y+i,L+i);
        --X[i]; --Y[i];
    }
}

void insert(int x, int y, int c)
{
    F[x][D[x]]=F[y][D[y]]=0;
    Poz[x][y]=D[x];
    Poz[y][x]=D[y];
    G[x][D[x]]=y;
    G[y][D[y]]=x;
    C[x][D[x]++]=c;
    C[y][D[y]++]=0;
}

int BFS()
{
    int l,r,i,x,y;

    Q[l=r=0]=source;
    for(i=0;i<node;++i)
        Pre[i]=-1;
    Min[source]=a; Pre[source]=-2;

    while(l<=r && Pre[sink]==-1)
    {
        x=Q[l++];
        for(i=0;i<D[x];++i)
        {
            y=G[x][i];
            if(Pre[y]==-1 && F[x][i]<C[x][i])
            {
                Pre[y]=x;
                Min[y]=min(Min[x],C[x][i]-F[x][i]);
                Q[++r]=y;
            }
        }
    }
    return Pre[sink]!=-1;
}

int max_flow(int t)
{
    int i,j,flow=0;

    source=(t+1)*n; sink=t*n; node=source+1;

    for(i=0;i<node;++i)
        D[i]=0;
    for(i=0;i<t;++i)
    {
        for(j=0;j<m;++j)
        {
            insert(i*n+X[j],(i+1)*n+Y[j],L[j]);
            insert(i*n+Y[j],(i+1)*n+X[j],L[j]);
        }
        for(j=0;j<n;++j)
            insert(i*n+j,(i+1)*n+j,a);
    }
    for(i=0;i<n;++i)
        insert(source,i,A[i]);

    while(BFS())
    {
        flow+=Min[sink];
        i=sink;
        while(i!=source)
        {
            F[Pre[i]][Poz[Pre[i]][i]]+=Min[sink];
            F[i][Poz[i][Pre[i]]]-=Min[sink];
            i=Pre[i];
        }
    }
    return flow;
}

int solve()
{
    int i,j,m;

    i=0; j=a+n;
    while(i<j)
    {
        m=i+j>>1;
        if(max_flow(m)==a)
            j=m;
        else
            i=m+1;
    }
    return i;
}

void write(int ans)
{
    freopen("algola.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    read();
    write(solve());
    return 0;
}