#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int nmax=55;
vector<int> v[nmax];
queue <pair<int,int> > q;
char c[nmax][nmax],fl[nmax][nmax][nmax];
bool how[nmax][nmax];
int prec[nmax][nmax];
int start,node,n,m,a,b,cap,i,j,source,timp,Time,maxtime,minfl,aux;
bool bfs()
{
   for(i=1;i<=n;i++)
    for(j=1;j<=max(50,n)+1;j++)
    prec[i][j]=0,how[i][j]=0;
    q.push(make_pair(source,0));prec[source][0]=-1;
   while(!q.empty())
   {
       start=q.front().first;
       timp=q.front().second;
       q.pop();
       for(i=0;i<v[start].size();i++)
       {
            node=v[start][i];
            if(prec[node][timp+1]==0&&fl[start][node][timp+1]<c[start][node])
            {
                prec[node][timp+1]=start;
                q.push(make_pair(node,timp+1));
            }
            if(timp>0&&prec[node][timp-1]==0&&fl[start][node][timp-1]<0)
            {
                prec[node][timp-1]=start;
                how[node][timp-1]=1;
                q.push(make_pair(node,timp-1));
            }
       }
   }
   for(i=1;i<=max(50,n)+1;i++)
   {
       if(prec[1][i])
       {
           Time=i;
           return 1;
       }
   }
   return 0;
}
int main()
{
    ifstream f("algola.in");
    ofstream g("algola.out");
    f>>n>>m;source=n+1;
    for(i=1;i<=n;i++)
    {
        f>>cap;
        v[source].push_back(i);
        c[source][i]=cap;
        v[i].push_back(i);
        c[i][i]=100;
    }
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>cap;
        v[a].push_back(b);
        v[b].push_back(a);
        c[a][b]=c[b][a]=cap;
    }
    while(bfs())
    {
        if(Time>maxtime)
            maxtime=Time;
        node=1;minfl=100;timp=Time;;
        while(node!=source)
        {
            minfl=min(minfl,c[prec[node][timp]][node]-fl[prec[node][timp]][node][timp]);
            aux=node;
            node=prec[node][timp];
            if(how[aux][timp]) timp++;
            else timp--;
        }
        node=1;timp=Time;
        while(node!=source)
        {
            fl[prec[node][timp]][node][timp]+=minfl;
            fl[node][prec[node][timp]][timp]-=minfl;
            aux=node;
            node=prec[node][timp];
            if(how[aux][timp]==1) timp++;
                else timp--;
        }
    }
    maxtime--;//reindexam de la 0
    g<<maxtime;
    return 0;
}