#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int nmax=55;
vector<int> v[nmax];
struct comp
{
    bool operator()(pair<int,int> unu,pair <int,int> doi)
    {
        return unu.second>doi.second;
    }
};
priority_queue < pair<int,int>,vector<pair<int,int> >,comp > q;
char c[nmax][nmax],fl[nmax][nmax][nmax];
int prec[nmax][nmax];
int start,node,n,m,a,b,cap,i,j,source,timp,Time,maxtime,minfl;
bool bfs()
{
   for(i=1;i<=n;i++)
    for(j=1;j<=n+1;j++)
    prec[i][j]=0;
    q.push(make_pair(source,0));prec[source][0]=-1;
   while(!q.empty())
   {
       start=q.top().first;
       timp=q.top().second;
       q.pop();
       if(start==1)
       {
           Time=timp;
           while(!q.empty())
            q.pop();
           return 1;
       }
       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]<0)
            {
                prec[node][timp-1]=start;
                q.push(make_pair(node,timp-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]);
            node=prec[node][timp];
            timp--;
        }
        node=1;timp=Time;
        while(node!=source)
        {
            fl[prec[node][timp]][node][timp]+=minfl;
            fl[node][prec[node][timp]][timp]-=minfl;
            node=prec[node][timp];
            timp--;
        }
    }
    maxtime--;//reindexam de la 0
    g<<maxtime;
    return 0;
}