#include <stdio.h>

#define maxN 60
#define maxt 100
#define maxn 5010
#define maxm 310
#define maxx 60010
#define inf 100

int N,m,n,sol,l,sum;
int b[maxN];
int x[maxm],y[maxm],z[maxm];
int g[maxn],from[maxn],s[maxn];
char c[maxn][maxn],f[maxn][maxn];
int a[maxx],found;

void Build(int X)
{
    int i,j;
	n=X*N;

	for (i=0;i<=n+1;i++) g[i]=0;

    for (i=0;i<=n;i++)
      for (j=0;j<=n;j++) 
      {
          c[i][j]=0;
          f[i][j]=0;
      }
      
    for (i=1;i<=N;i++)
    {
        g[0]++;
        g[(X-1)*N+i]++;
        c[0][(X-1)*N+i]=b[i];
	}
    
    for (i=1;i<X;i++) 
    {
      for (j=1;j<=m;j++)
      {
		  g[i*N+x[j]]++;
		  g[i*N+y[j]]++;
		  g[(i-1)*N+x[j]]++;
		  g[(i-1)*N+y[j]]++;
		  c[i*N+x[j]][(i-1)*N+y[j]]=z[j];
		  c[i*N+y[j]][(i-1)*N+x[j]]=z[j];
	  }

	  for (j=1;j<=N;j++)
	  {
		  g[i*N+j]++;
		  g[(i-1)*N+j]++;
		  c[i*N+j][(i-1)*N+j]=inf;
	  }
	}

	for (i=1;i<=n+1;i++) g[i]+=g[i-1];

    for (i=1;i<=N;i++)
    {
        a[g[0]--]=(X-1)*N+i;
		a[g[(X-1)*N+i]--]=0;
    }

	for (i=1;i<X;i++)
	{
	  for (j=1;j<=m;j++)
	  {
		  a[g[i*N+x[j]]--]=(i-1)*N+y[j];
		  a[g[i*N+y[j]]--]=(i-1)*N+x[j];
		  a[g[(i-1)*N+x[j]]--]=i*N+y[j];
		  a[g[(i-1)*N+y[j]]--]=i*N+x[j];
	  }

	  for (j=1;j<=N;j++)
	  {
		  a[g[i*N+j]--]=(i-1)*N+j;
		  a[g[(i-1)*N+j]--]=i*N+j;
	  }
	}

    for (i=0;i<=n+1;i++) g[i]++;
}

int BFS(int nod)
{
    int i,j,min;
    
	for (i=0;i<=n;i++) from[i]=-1;
	from[nod]=0;
    l=1;
    i=1;
    s[l]=nod;
    
    while (i<=l)
    {
          for (j=g[s[i]];j<g[s[i]+1];j++)
			if ((from[a[j]]==-1) && (c[s[i]][a[j]]-f[s[i]][a[j]]>0))
            {
                from[a[j]]=s[i];
                s[++l]=a[j];
                
                if (s[l]==1)
                {
                    i=l+1;
                    found=1;
                    break; 
                }
            }
          i++;
    }    
    
    if (found)
    {
        i=1;
        
		while (i!=nod)
        {
              if (c[from[i]][i]-f[from[i]][i]<min) min=c[from[i]][i]-f[from[i]][i];
			  i=from[i];
        }
        
        i=1;
        while (i!=nod)
        {
              f[from[i]][i]+=min;
              f[i][from[i]]-=min;
              i=from[i];
        }
        
        return min;
    }
    return 0;
}

int works()
{
    int flux=0;
    found=1;
    
	while ((flux<sum) && (found))
    {
          found=0;
          flux+=BFS(0);
    }
    
    return flux==sum;
}

int main()
{
    freopen("algola.in","r",stdin);
    freopen("algola.out","w",stdout);
    
    int i,j;
    
    scanf("%d %d",&N,&m);
    
    for (i=1;i<=N;i++) 
    {
        scanf("%d",&b[i]);
        sum+=b[i];
    }
    
	for (i=1;i<=m;i++) scanf("%d %d %d",&x[i],&y[i],&z[i]);

	int front=1,middle,back=maxt;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
		  Build(middle);
          
		  if (works())
          {
				 sol=middle;
                 back=middle-1;
          }
          else front=middle+1;
    }
    
	printf("%d\n",sol-1);
    
    return 0;
}