#include <stdio.h>

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

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

void Build(int X)
{
    int i,j,p,q;
	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;
      }
      
    p=(X-1)*N;
    for (i=1;i<=N;++i)
    {
        g[0]++;
        g[p+i]++;
        c[0][p+i]=b[i];
	}
    
    for (i=1;i<X;++i) 
    {
      p=i*N;
      q=(i-1)*N;
      for (j=1;j<=m;++j)
      {
		  g[p+x[j]]++;
		  g[p+y[j]]++;
		  g[q+x[j]]++;
		  g[q+y[j]]++;
		  c[p+x[j]][q+y[j]]=z[j];
		  c[p+y[j]][q+x[j]]=z[j];
	  }

	  for (j=1;j<=N;++j)
	  {
		  g[p+j]++;
		  g[q+j]++;
		  c[p+j][q+j]=inf;
	  }
	}

	for (i=1;i<=n+1;++i) g[i]+=g[i-1];
	
	p=(X-1)*N;

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

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

	  for (j=1;j<=N;++j)
	  {
		  a[g[p+j]--]=q+j;
		  a[g[q+j]--]=p+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;
}